Home » Keyword index

maximum clique


Graph Theory » Coloring » Vertex coloring

2-colouring a graph without a monochromatic maximum clique ★★

Author(s): Hoang; McDiarmid

Conjecture   If $ G $ is a non-empty graph containing no induced odd cycle of length at least $ 5 $, then there is a $ 2 $-vertex colouring of $ G $ in which no maximum clique is monochromatic.

Keywords: maximum clique; Partitioning

Posted by Jon Noel
updated August 25th, 2013
add new comment
Syndicate content