# 2-colouring a graph without a monochromatic maximum clique

 Importance: Medium ✭✭
 Author(s): Hoang, Chinh T. McDiarmid, Colin
 Subject: Graph Theory » Coloring » » Vertex coloring
 Keywords: maximum clique Partitioning
 Posted by: Jon Noel on: August 25th, 2013
Conjecture   If is a non-empty graph containing no induced odd cycle of length at least , then there is a -vertex colouring of in which no maximum clique is monochromatic.

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.