Hoang, Chinh T.


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

Hoàng-Reed Conjecture ★★★

Author(s): Hoang; Reed

Conjecture   Every digraph in which each vertex has outdegree at least $ k $ contains $ k $ directed cycles $ C_1, \ldots, C_k $ such that $ C_j $ meets $ \cup_{i=1}^{j-1}C_i $ in at most one vertex, $ 2 \leq j \leq k $.

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 $ G $ and for every vertex $ v \in V(G) $ a subset $ \ell(v) $ of $ \{1,2,3,4\} $, and decides if there exists a partition of $ V(G) $ into $ \{A_1,A_2,A_3,A_4\} $ so that $ v \in A_i $ only if $ i \in \ell(v) $ and so that $ A_1,A_2 $ are independent, $ A_4 $ is a clique, and there are no edges between $ A_1 $ and $ A_3 $?

Keywords: list partition; polynomial algorithm

Syndicate content