Recent Activity

Subgraph of large average degree and large girth. ★★

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$ .

Keywords:

Posted by fhavet
updated March 5th, 2013

add new comment

Graph Theory

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.

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}))$ .

Keywords:

Posted by fhavet
updated March 5th, 2013

add new comment

Graph Theory » Directed Graphs

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

Author(s): Mader

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$ .

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

Graph Theory » Topological G.T.

Large induced forest in a planar graph. ★★

Author(s): Abertson; Berman

Conjecture Every planar graph on $n$ verices has an induced forest with at least $n/2$ vertices.

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

Graph Theory

Lovász Path Removal Conjecture ★★

Author(s): Lovasz

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.

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

Graph Theory » Basic G.T. » Paths

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

Author(s): Kelmans

Problem Does every $3$ -connected cubic graph on $3k$ vertices admit a partition into $k$ paths of length $2$ ?

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

Graph Theory » Basic G.T. » Cycles

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

Author(s): Sabidussi

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$ .

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

Graph Theory » Basic G.T. » Cycles

Decomposing an eulerian graph into cycles. ★★

Author(s): Hajós

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

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

Graph Theory » Basic G.T. » Paths

Decomposing a connected graph into paths. ★★★

Author(s): Gallai

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

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Melnikov's valency-variety problem ★

Author(s): Melnikov

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)} } ~ ?$

Keywords:

Posted by asp
updated March 3rd, 2013

add new comment

Graph Theory » Coloring

Coloring the union of degenerate graphs ★★

Author(s): Tarsi

Conjecture The union of a $1$ -degenerate graph (a forest) and a $2$ -degenerate graph is $5$ -colourable.

Keywords:

Posted by fhavet
updated March 3rd, 2013

add new comment

Graph Theory

Arc-disjoint strongly connected spanning subdigraphs ★★

Author(s): Bang-Jensen; Yeo

Conjecture There exists an ineteger $k$ so that every $k$ -arc-connected digraph contains a pair of arc-disjoint strongly connected spanning subdigraphs?

Keywords:

Posted by fhavet
updated March 2nd, 2013

add new comment

Graph Theory » Directed Graphs

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

Author(s): Thomassen

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.

Keywords:

Posted by fhavet
updated March 2nd, 2013

add new comment

Graph Theory » Coloring » Edge coloring

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$ .

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.}$

Keywords:

Posted by fhavet
updated March 1st, 2013

add new comment

Graph Theory » Directed Graphs

Long directed cycles in diregular digraphs ★★★

Author(s): Jackson

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$ .

Keywords:

Posted by fhavet
updated March 1st, 2013

add new comment

Graph Theory » Directed Graphs

Splitting a digraph with minimum outdegree constraints ★★★

Author(s): Alon

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$ ?

Keywords:

Posted by fhavet
updated March 1st, 2013

add new comment

Graph Theory