Recent Activity

Decomposing k-arc-strong tournament into k spanning strong digraphs ★★

Author(s): Bang-Jensen; Yeo

\begin{conjecture} Every k-arc-strong tournament decomposes into k spanning strong digraphs. \end{conjecture}


PTAS for feedback arc set in tournaments ★★

Author(s): Ailon; Alon

\begin{question} Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments? \end{question}

Keywords: feedback arc set; PTAS; tournament

Partitionning a tournament into k-strongly connected subtournaments. ★★

Author(s): Thomassen

\begin{problem} Let $k_1, \dots , k_p$ be positve integer Does there exists an integer $g(k_1, \dots , k_p)$ such that every $g(k_1, \dots , k_p)$-strong tournament $T$ admits a partition $(V_1\dots , V_p)$ of its vertex set such that the subtournament induced by $V_i$ is a non-trivial $k_i$-strong for all $1\leq i\leq p$. \end{problem}


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}


Colouring the square of a planar graph ★★

Author(s): Wegner

\begin{conjecture} Let $G$ be a planar graph of maximum degree $\Delta$. The chromatic number of its square is \begin{itemize} \item at most $7$ if $\Delta =3$, \item at most $\Delta+5$ if $4\leq\Delta\leq 7$, \item at most $\left\lfloor\frac32\,\Delta\right\rfloor+1$ if $\Delta\ge8$. \end{itemize} \end{conjecture}


List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

\begin{conjecture} There is a constant $c$ such that the list chromatic number of any bipartite graph $G$ of maximum degree $\Delta$ is at most $c \log \Delta$. % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}


Hamilton decomposition of prisms over 3-connected cubic planar graphs ★★

Author(s): Alspach; Rosenfeld

\begin{conjecture} Every prism over a $3$-connected cubic planar graph can be decomposed into two Hamilton cycles. \end{conjecture}


Turán's problem for hypergraphs ★★

Author(s): Turan

\begin{conjecture} Every simple $3$-uniform hypergraph on $3n$ vertices which contains no complete $3$-uniform hypergraph on four vertices has at most $\frac12 n^2(5n-3)$ hyperedges. \end{conjecture}

\begin{conjecture} Every simple $3$-uniform hypergraph on $2n$ vertices which contains no complete $3$-uniform hypergraph on five vertices has at most $n^2(n-1)$ hyperedges. \end{conjecture}


4-connected graphs are not uniquely hamiltonian ★★

Author(s): Fleischner

\begin{conjecture} Every $4$-connected graph with a Hamilton cycle has a second Hamilton cycle. \end{conjecture}


Every prism over a 3-connected planar graph is hamiltonian. ★★

Author(s): Kaiser; Král; Rosenfeld; Ryjácek; Voss

\begin{conjecture} If $G$ is a $3$-connected planar graph, then $G\square K_2$ has a Hamilton cycle. \end{conjecture}


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}


Edge-disjoint Hamilton cycles in highly strongly connected tournaments. ★★

Author(s): Thomassen

\begin{conjecture} For every $k\geq 2$, there is an integer $f(k)$ so that every strongly $f(k)$-connected tournament has $k$ edge-disjoint Hamilton cycles. \end{conjecture}


Hamilton cycle in small d-diregular graphs ★★

Author(s): Jackson

An directed graph is $k$-diregular if every vertex has indegree and outdegree at least $k$.

\begin{conjecture} For $d >2$, every $d$-diregular oriented graph on at most $4d+1$ vertices has a Hamilton cycle. \end{conjecture}


Switching reconstruction of digraphs ★★

Author(s): Bondy; Mercier

\begin{question} Are there any switching-nonreconstructible digraphs on twelve or more vertices? \end{question}


Switching reconstruction conjecture ★★

Author(s): Stanley

\begin{conjecture} Every simple graph on five or more vertices is switching-reconstructible. \end{conjecture}

Keywords: reconstruction

Every 4-connected toroidal graph has a Hamilton cycle ★★

Author(s): Grunbaum; Nash-Williams

\begin{conjecture} Every 4-connected toroidal graph has a Hamilton cycle. \end{conjecture}


Acyclic list colouring of planar graphs. ★★★

Author(s): Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena

\begin{conjecture} Every planar graph is acyclically 5-choosable. \end{conjecture}


Earth-Moon Problem ★★

Author(s): Ringel

\begin{problem} What is the maximum number of colours needed to colour countries such that no two countries sharing a common border have the same colour in the case where each country consists of one region on earth and one region on the moon ? \end{problem}


Triangle-packing vs triangle edge-transversal. ★★

Author(s): Tuza

\begin{conjecture} If $G$ has at most $k$ edge-disjoint triangles, then there is a set of $2k$ edges whose deletion destroys every triangle. \end{conjecture}


Odd-cycle transversal in triangle-free graphs ★★

Author(s): Erdos; Faudree; Pach; Spencer

\begin{conjecture} If $G$ is a simple triangle-free graph, then there is a set of at most $n^2/25$ edges whose deletion destroys every odd cycle. \end{conjecture}