Graph Theory » Graph Algorithms

PTAS for feedback arc set in tournaments ★★

Author(s): Ailon; Alon

Question   Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?

Keywords: feedback arc set; PTAS; tournament

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

Partitionning a tournament into k-strongly connected subtournaments. ★★

Author(s): Thomassen

Problem   Let $ k_1, \dots , k_p $ be positve integer Does there exists an integer $ g(k_1, \dots , k_p) $ such that every $ g(k_1, \dots , k_p) $-strong tournament $ T $ admits a partition $ (V_1\dots , V_p) $ of its vertex set such that the subtournament induced by $ V_i $ is a non-trivial $ k_i $-strong for all $ 1\leq i\leq p $.

Keywords:

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

Weighted colouring of hexagonal graphs. ★★

Author(s): McDiarmid; Reed

Conjecture   There is an absolute constant $ c $ such that for every hexagonal graph $ G $ and vertex weighting $ p:V(G)\rightarrow \mathbb{N} $, $$\chi(G,p) \leq \frac{9}{8}\omega(G,p) + c $$

Keywords:

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

Colouring the square of a planar graph ★★

Author(s): Wegner

Conjecture   Let $ G $ be a planar graph of maximum degree $ \Delta $. The chromatic number of its square is
    \item at most $ 7 $ if $ \Delta =3 $, \item at most $ \Delta+5 $ if $ 4\leq\Delta\leq 7 $, \item at most $ \left\lfloor\frac32\,\Delta\right\rfloor+1 $ if $ \Delta\ge8 $.

Keywords:

Posted by fhavet
updated March 13th, 2013
add new comment | 1 attachment
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