![](/files/happy5.png)
McDiarmid, Colin
2-colouring a graph without a monochromatic maximum clique ★★
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.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ 5 $](/files/tex/87f5fe1d4b06035debb52cf2d67802fbfa9cb4ab.png)
![$ 2 $](/files/tex/5271e36bb1c040e0f14061d89cd97d0c86d4e06f.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
Keywords: maximum clique; Partitioning
Arc-disjoint directed cycles in regular directed graphs ★★
Author(s): Alon; McDiarmid; Molloy
Conjecture If
is a
-regular directed graph with no parallel arcs, then
contains a collection of
arc-disjoint directed cycles.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ {k+1 \choose 2} $](/files/tex/783a85f7ae121a116b289d0f5b090f98fc9f959e.png)
Keywords:
Weighted colouring of hexagonal graphs. ★★
Conjecture There is an absolute constant
such that for every hexagonal graph
and vertex weighting
,
![$ c $](/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ p:V(G)\rightarrow \mathbb{N} $](/files/tex/6b14cbdc1cda96520fd87d9507b262f943ccf8ba.png)
![$$\chi(G,p) \leq \frac{9}{8}\omega(G,p) + c $$](/files/tex/9b4ccf7620c2a90a97c40177afd9201723864ba8.png)
Keywords:
![Syndicate content Syndicate content](/misc/feed.png)