Home

Recent Activity

Graph Theory » Coloring » Vertex coloring

List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

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

Keywords:

Posted by fhavet
updated March 12th, 2013
add new comment
Graph Theory » Basic G.T. » Cycles

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

Author(s): Alspach; Rosenfeld

Conjecture   Every prism over a $ 3 $-connected cubic planar graph can be decomposed into two Hamilton cycles.

Keywords:

Posted by fhavet
updated March 12th, 2013
add new comment
Graph Theory » Hypergraphs

Turán's problem for hypergraphs ★★

Author(s): Turan

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

Keywords:

Posted by fhavet
updated March 12th, 2013
add new comment
Graph Theory » Basic G.T. » Cycles

4-connected graphs are not uniquely hamiltonian ★★

Author(s): Fleischner

Conjecture   Every $ 4 $-connected graph with a Hamilton cycle has a second Hamilton cycle.

Keywords:

Posted by fhavet
updated March 11th, 2013
add new comment
Graph Theory » Basic G.T. » Cycles

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

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

Conjecture   If $ G $ is a $ 3 $-connected planar graph, then $ G\square K_2 $ has a Hamilton cycle.

Keywords:

Posted by fhavet
updated March 11th, 2013
add new comment
Graph Theory » Directed Graphs

Hoàng-Reed Conjecture ★★★

Author(s): Hoang; Reed

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

Keywords:

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

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

Author(s): Thomassen

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.

Keywords:

Posted by fhavet
updated March 8th, 2013
add new comment
Graph Theory » Directed Graphs

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

Conjecture   For $ d >2 $, every $ d $-diregular oriented graph on at most $ 4d+1 $ vertices has a Hamilton cycle.

Keywords:

Posted by fhavet
updated March 8th, 2013
add new comment
Graph Theory

Switching reconstruction of digraphs ★★

Author(s): Bondy; Mercier

Question   Are there any switching-nonreconstructible digraphs on twelve or more vertices?

Keywords:

Posted by fhavet
updated March 7th, 2013
add new comment
Graph Theory

Switching reconstruction conjecture ★★

Author(s): Stanley

Conjecture   Every simple graph on five or more vertices is switching-reconstructible.

Keywords: reconstruction

Posted by fhavet
updated March 7th, 2013
add new comment
Graph Theory » Topological G.T.

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

Author(s): Grunbaum; Nash-Williams

Conjecture   Every 4-connected toroidal graph has a Hamilton cycle.

Keywords:

Posted by fhavet
updated March 7th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Acyclic list colouring of planar graphs. ★★★

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

Conjecture   Every planar graph is acyclically 5-choosable.

Keywords:

Posted by fhavet
updated March 7th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Earth-Moon Problem ★★

Author(s): Ringel

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 ?

Keywords:

Posted by fhavet
updated March 6th, 2013
add new comment
Graph Theory » Extremal G.T.

Triangle-packing vs triangle edge-transversal. ★★

Author(s): Tuza

Conjecture   If $ G $ has at most $ k $ edge-disjoint triangles, then there is a set of $ 2k $ edges whose deletion destroys every triangle.

Keywords:

Posted by fhavet
updated March 6th, 2013
add new comment
Graph Theory » Extremal G.T.

Odd-cycle transversal in triangle-free graphs ★★

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

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.

Keywords:

Posted by fhavet
updated March 6th, 2013
add new comment
Graph Theory » Hypergraphs

Simultaneous partition of hypergraphs ★★

Author(s): Kühn; Osthus

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

Keywords:

Posted by fhavet
updated March 6th, 2013
add new comment
Graph Theory » Extremal G.T.

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

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?

Keywords:

Posted by fhavet
updated March 5th, 2013
add new comment
Graph Theory » Basic G.T.

Subgraph of large average degree and large girth. ★★

Author(s): Thomassen

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