![](/files/happy5.png)
2-colouring a graph without a monochromatic maximum clique
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ 5 $](/files/tex/87f5fe1d4b06035debb52cf2d67802fbfa9cb4ab.png)
![$ 2 $](/files/tex/5271e36bb1c040e0f14061d89cd97d0c86d4e06f.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
A -division of a graph
is a partitioning of
into two subgraphs, neither of which contains a maximum clique. It is known that every perfect graph admits a
-division. Thus, by the Strong Perfect Graph Theorem [CRS], a graph which does not contain an induced copy of an odd cycle of length at least
or its complement has a
-division. Hoàng and McDiarmid [HMcD] also prove that a claw-free graph admits a 2-division if and only if it does not contain an induced odd cycle of length at least
. The conjecture says that this holds for all graphs.
This problem was featured as unsolved problem #49 in Bondy and Murty's book "Graph Theory" [BM].
See also a posting on the American Institute of Mathematics website, contributed by Bruce Reed.
Bibliography
[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: The strong perfect graph theorem, Ann. of Math. (2) 164 (2006), no. 1, 51--229. MathSciNet
[HMcD] C.T. Hoàng, C. McDiarmid, On the divisibility of graphs, Discrete Math. 242 (1–3) (2002) 145–156.
[BM] J. A. Bondy and U. S. R. Murty. Graph theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, 2008.
* indicates original appearance(s) of problem.