Home » Keyword index

edge-connectivity


Graph Theory » Basic G.T. » Connectivity

Kriesell's Conjecture ★★

Author(s): Kriesell

Conjecture   Let $ G $ be a graph and let $ T\subseteq V(G) $ such that for any pair $ u,v\in T $ there are $ 2k $ edge-disjoint paths from $ u $ to $ v $ in $ G $. Then $ G $ contains $ k $ edge-disjoint trees, each of which contains $ T $.

Keywords: Disjoint paths; edge-connectivity; spanning trees

Posted by Jon Noel
updated August 25th, 2013
add new comment
Graph Theory » Basic G.T. » Connectivity

Partitioning edge-connectivity ★★

Author(s): DeVos

Question   Let $ G $ be an $ (a+b+2) $-edge-connected graph. Does there exist a partition $ \{A,B\} $ of $ E(G) $ so that $ (V,A) $ is $ a $-edge-connected and $ (V,B) $ is $ b $-edge-connected?

Keywords: edge-coloring; edge-connectivity

Posted by mdevos
updated March 7th, 2007
add new comment
Graph Theory » Coloring » Nowhere-zero flows

(2 + epsilon)-flow conjecture ★★★

Author(s): Goddyn; Seymour

Conjecture   For every $ \epsilon>0 $ there exists an integer $ k $ so that every $ k $-edge-connected graph has a $ (2+\epsilon) $-flow.

Keywords: edge-connectivity; flow

Posted by mdevos
updated February 19th, 2020
1 comment
Syndicate content