Consider a graph G on kr vertices. We say that G is strongly r-colourable if for any partition of V (G) into parts V1,..., Vk, each of size r, G has a r-colouring such that every colour class contains exactly one vertex from each part (and so every part contains exactly one vertex of each colour). Equivalently, G is strongly r-colourable if for any graph G′ which is the union of k disjoint r-cliques on the same vertex set, χ(G U G) = r. A well-known conjecture of Erdős, recently proven by Fleischner and Steibitz , states that the union of a Hamilton cycle on 3n vertices and n vertex disjoint triangles on the same vertex set has chromatic number 3. In other words, C3 n is strongly 3-colourable. Strongly r-colourable graphs are of interest partially because of their relationship to this problem, and also because they have other applications (see for example, Exercise 8.1).
Weitere Kapitel dieses Buchs durch Wischen aufrufen
- The Strong Chromatic Number
- Springer Berlin Heidelberg
Pluta Logo/© Pluta, Rombach Rechtsanwälte/© Rombach Rechtsanwälte