Graph Theory

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

Author(s): Gallai

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

Keywords:

Posted by fhavet
updated October 14th, 2023
1 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