![](/files/happy5.png)
Hoang, Chinh T.
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
Hoàng-Reed Conjecture ★★★
Conjecture Every digraph in which each vertex has outdegree at least
contains
directed cycles
such that
meets
in at most one vertex,
.
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ C_1, \ldots, C_k $](/files/tex/0df670e43d33838d6e04e86a590da56100880e60.png)
![$ C_j $](/files/tex/b1365660549601f059d1b19f13f120a8fd821c25.png)
![$ \cup_{i=1}^{j-1}C_i $](/files/tex/b45609a301fcc110ef904d9f320f045d3947da71.png)
![$ 2 \leq j \leq k $](/files/tex/f4a8b4068d7bbb76eee5a6457f5fa87ff65184f1.png)
Keywords:
The stubborn list partition problem ★★
Author(s): Cameron; Eschen; Hoang; Sritharan
Problem Does there exist a polynomial time algorithm which takes as input a graph
and for every vertex
a subset
of
, and decides if there exists a partition of
into
so that
only if
and so that
are independent,
is a clique, and there are no edges between
and
?
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ v \in V(G) $](/files/tex/1466419f1101030390df1795c6f6a568ac18776b.png)
![$ \ell(v) $](/files/tex/fa7556a65d20c6dbe9ae8911f5247691d913dca7.png)
![$ \{1,2,3,4\} $](/files/tex/de0625f2e589e27a7b57cc4b66560e0e0d0e5daf.png)
![$ V(G) $](/files/tex/b324b54d8674fa66eb7e616b03c7a601ccdab6b8.png)
![$ \{A_1,A_2,A_3,A_4\} $](/files/tex/332fca63ad23d0f750116b00770cf8b73f25bf0b.png)
![$ v \in A_i $](/files/tex/526a8824e06e79af8564522aa70897d4c46c6fdc.png)
![$ i \in \ell(v) $](/files/tex/aa7e74539033b93194f38cd4ef8273a0543143b5.png)
![$ A_1,A_2 $](/files/tex/abb6004b066dae60842422a05109dd268e25b013.png)
![$ A_4 $](/files/tex/50c3d5221f6420416edde366fd2b081acada5bfe.png)
![$ A_1 $](/files/tex/cad9bfcb5f598c9f3e6780be0cf006515579b1fb.png)
![$ A_3 $](/files/tex/1979729d0d75e585787ae2a135d16b37f3e434f2.png)
Keywords: list partition; polynomial algorithm
![Syndicate content Syndicate content](/misc/feed.png)