McDiarmid, Colin

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

Arc-disjoint directed cycles in regular directed graphs ★★

Author(s): Alon; McDiarmid; Molloy

\begin{conjecture} If $G$ is a $k$-regular directed graph with no parallel arcs, then $G$ contains a collection of ${k+1 \choose 2}$ arc-disjoint directed cycles. \end{conjecture}


Weighted colouring of hexagonal graphs. ★★

Author(s): McDiarmid; Reed

\begin{conjecture} There is an absolute constant $c$ such that for every hexagonal graph $G$ and vertex weighting $p:V(G)\rightarrow \mathbb{N}$, $$\chi(G,p) \leq \frac{9}{8}\omega(G,p) + c $$ \end{conjecture}


Syndicate content