Home

Recent Activity

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

Stable set meeting all longest directed paths. ★★

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

Conjecture   Every digraph has a stable set meeting all longest directed paths

Keywords:

Posted by fhavet
updated March 1st, 2013
add new comment
Graph Theory » Directed Graphs

Ádám's Conjecture ★★★

Author(s): Ádám

Conjecture   Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles.

Keywords:

Posted by fhavet
updated March 1st, 2013
add new comment
Graph Theory » Directed Graphs

Caccetta-Häggkvist Conjecture ★★★★

Author(s): Caccetta; Häggkvist

Conjecture   Every simple digraph of order $ n $ with minimum outdegree at least $ r $ has a cycle with length at most $ \lceil n/r\rceil $

Keywords:

Posted by fhavet
updated February 28th, 2013
add new comment
Graph Theory » Directed Graphs

Directed path of length twice the minimum outdegree ★★★

Author(s): Thomassé

Conjecture   Every oriented graph with minimum outdegree $ k $ contains a directed path of length $ 2k $.

Keywords:

Posted by fhavet
updated February 28th, 2013
add new comment
Graph Theory » Directed Graphs

Antidirected trees in digraphs ★★

Author(s): Addario-Berry; Havet; Linhares Sales; Reed; Thomassé

An antidirected tree is an orientation of a tree in which every vertex has either indegree 0 or outdergree 0.

Conjecture   Let $ D $ be a digraph. If $ |A(D)| > (k-2) |V(D)| $, then $ D $ contains every antidirected tree of order $ k $.

Keywords:

Posted by fhavet
updated February 26th, 2013
add new comment
Graph Theory » Directed Graphs » Tournaments

Decomposing an even tournament in directed paths. ★★★

Author(s): Alspach; Mason; Pullman

Conjecture   Every tournament $ D $ on an even number of vertices can be decomposed into $ \sum_{v\in V}\max\{0,d^+(v)-d^-(v)\} $ directed paths.

Keywords:

Posted by fhavet
updated February 26th, 2013
add new comment
Graph Theory » Directed Graphs

Oriented trees in n-chromatic digraphs ★★★

Author(s): Burr

Conjecture   Every digraph with chromatic number at least $ 2k-2 $ contains every oriented tree of order $ k $ as a subdigraph.

Keywords:

Posted by fhavet
updated February 25th, 2013
add new comment