maximum clique


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

Author(s): Hoang; McDiarmid

\begin{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. \end{conjecture}

Keywords: maximum clique; Partitioning

Syndicate content