Hoang, Chinh T.


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

Hoàng-Reed Conjecture ★★★

Author(s): Hoang; Reed

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

Keywords:

The stubborn list partition problem ★★

Author(s): Cameron; Eschen; Hoang; Sritharan

\begin{problem} Does there exist a \Def{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$? \end{problem}

Keywords: list partition; polynomial algorithm

Syndicate content