Recent Activity

Simultaneous partition of hypergraphs ★★

Author(s): Kühn; Osthus

\begin{problem} Let $H_1$ and $H_2$ be two $r$-uniform hypergraph on the same vertex set $V$. Does there always exist a partition of $V$ into $r$ classes $V_1, \dots , V_r$ such that for both $i=1,2$, at least $r!m_i/r^r -o(m_i)$ hyperedges of $H_i$ meet each of the classes $V_1, \dots , V_r$? \end{problem}

Keywords:

Complexity of the H-factor problem. ★★

Author(s): Kühn; Osthus

An $H$-factor in a graph $G$ is a set of vertex-disjoint copies of $H$ covering all vertices of $G$. \begin{problem}Let $c$ be a fixed positive real number and $H$ a fixed graph. Is it NP-hard to determine whether a graph $G$ on $n$ vertices and minimum degree $cn$ contains and $H$-factor?% Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{problem}

Keywords:

Subgraph of large average degree and large girth. ★★

Author(s): Thomassen

\begin{conjecture} For all positive integers $g$ and $k$, there exists an integer $d$ such that every graph of average degree at least $d$ contains a subgraph of average degree at least $k$ and girth greater than $g$. \end{conjecture}

Keywords:

Turán number of a finite family. ★★

Author(s): Erdos; Simonovits

Given a finite family ${\cal F}$ of graphs and an integer $n$, the Turán number $ex(n,{\cal F})$ of ${\cal F}$ is the largest integer $m$ such that there exists a graph on $n$ vertices with $m$ edges which contains no member of ${\cal F}$ as a subgraph.

\begin{conjecture} For every finite family ${\cal F}$ of graphs there exists an $F\in {\cal F}$ such that $ex(n, F ) = O(ex(n, {\cal F}))$ .% Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords:

Subdivision of a transitive tournament in digraphs with large outdegree. ★★

Author(s): Mader

\begin{conjecture} For all $k$ there is an integer $f(k)$ such that every digraph of minimum outdegree at least $f(k)$ contains a subdivision of a transitive tournament of order $k$. \end{conjecture}

Keywords:

Large induced forest in a planar graph. ★★

Author(s): Abertson; Berman

\begin{conjecture} Every planar graph on $n$ verices has an induced forest with at least $n/2$ vertices. \end{conjecture}

Keywords:

Lovász Path Removal Conjecture ★★

Author(s): Lovasz

\begin{conjecture} There is an integer-valued function $f(k)$ such that if $G$ is any $f(k)$-connected graph and $x$ and $y$ are any two vertices of $G$, then there exists an induced path $P$ with ends $x$ and $y$ such that $G-V(P)$ is $k$-connected. \end{conjecture}

Keywords:

Partition of a cubic 3-connected graphs into paths of length 2. ★★

Author(s): Kelmans

\begin{problem} Does every $3$-connected cubic graph on $3k$ vertices admit a partition into $k$ paths of length $2$? \end{problem}

Keywords:

Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour. ★★

Author(s): Sabidussi

\begin{conjecture} Let $G$ be an eulerian graph of minimum degree $4$, and let $W$ be an eulerian tour of $G$. Then $G$ admits a decomposition into cycles none of which contains two consecutive edges of $W$. \end{conjecture}

Keywords:

Decomposing an eulerian graph into cycles. ★★

Author(s): Hajós

\begin{conjecture} Every simple eulerian graph on $n$ vertices can be decomposed into at most $\frac{1}{2}(n-1)$ cycles. \end{conjecture}

Keywords:

Decomposing a connected graph into paths. ★★★

Author(s): Gallai

\begin{conjecture} Every simple connected graph on $n$ vertices can be decomposed into at most $\frac{1}{2}(n+1)$ paths. \end{conjecture}

Keywords:

Melnikov's valency-variety problem

Author(s): Melnikov

\begin{problem} The valency-variety $w(G)$ of a graph $G$ is the number of different degrees in $G$. Is the chromatic number of any graph $G$ with at least two vertices greater than $$\ceil{ \frac{\floor{w(G)/2}}{|V(G)| - w(G)} } ~ ?$$ \end{problem}

Keywords:

Do any three longest paths in a connected graph have a vertex in common? ★★

Author(s): Gallai

\begin{conjecture} Do any three longest paths in a connected graph have a vertex in common? \end{conjecture}

Keywords:

Coloring the union of degenerate graphs ★★

Author(s): Tarsi

\begin{conjecture} The union of a $1$-degenerate graph (a forest) and a $2$-degenerate graph is $5$-colourable. \end{conjecture}

Keywords:

Arc-disjoint strongly connected spanning subdigraphs ★★

Author(s): Bang-Jensen; Yeo

\begin{conjecture} There exists an ineteger $k$ so that every $k$-arc-connected digraph contains a pair of arc-disjoint strongly connected spanning subdigraphs? \end{conjecture}

Keywords:

Arc-disjoint out-branching and in-branching ★★

Author(s): Thomassen

\begin{conjecture} There exists an integer $k$ such that every $k$-arc-strong digraph $D$ with specified vertices $u$ and $v$ contains an out-branching rooted at $u$ and an in-branching rooted at $v$ which are arc-disjoint.

% Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords:

Strong edge colouring conjecture ★★

Author(s): Erdos; Nesetril

A strong edge-colouring of a graph $G$ is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index $s\chi'(G)$ is the minimum number of colours in a strong edge-colouring of $G$.

\begin{conjecture} $$s\chi'(G) \leq \frac{5\Delta^2}{4}, \text{if $\Delta$ is even,}$$ $$s\chi'(G) \leq \frac{5\Delta^2-2\Delta +1}{4},&\text{if $\Delta$ is odd.}$$ \end{conjecture}

Keywords:

Long directed cycles in diregular digraphs ★★★

Author(s): Jackson

\begin{conjecture} Every strong oriented graph in which each vertex has indegree and outdegree at least $d$ contains a directed cycle of length at least $2d+1$. \end{conjecture}

Keywords:

Splitting a digraph with minimum outdegree constraints ★★★

Author(s): Alon

\begin{problem} Is there a minimum integer $f(d)$ such that the vertices of any digraph with minimum outdegree $d$ can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least $d$? \end{problem}

Keywords:

Stable set meeting all longest directed paths. ★★

Author(s): Laborde; Payan; Xuong N.H.

\begin{conjecture} Every digraph has a stable set meeting all longest directed paths \end{conjecture}

Keywords: