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