Cycles intersecting edge-cuts of prescribed sizes

被引:19
作者
Kaiser, Tomas [1 ,2 ]
Skrekovski, Riste [3 ,4 ]
机构
[1] Univ W Bohemia, Dept Math, Plzen 30614, Czech Republic
[2] Univ W Bohemia, Inst Theoret Comp Sci, Plzen 30614, Czech Republic
[3] Univ Ljubljana, Dept Math, Ljubljana 1111, Slovenia
[4] Charles Univ Prague, Inst Theoret Comp Sci, CR-11800 Prague 1, Czech Republic
关键词
graph; edge-cut; coverable set; dominating cycle;
D O I
10.1137/070683635
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We prove that every cubic bridgeless graph G contains a 2-factor which intersects all (minimal) edge-cuts of size 3 or 4. This generalizes an earlier result of the authors, namely that such a 2-factor exists provided that G is planar. As a further extension, we show that every graph contains a cycle ( a union of edge-disjoint circuits) that intersects all edge-cuts of size 3 or 4. Motivated by this result, we introduce the concept of a coverable set of integers and discuss a number of questions, some of which are related to classical problems of graph theory such as Tutte's 4-flow conjecture and the Dominating Cycle Conjecture.
引用
收藏
页码:861 / 874
页数:14
相关论文
共 16 条
[1]  
[Anonymous], PROGR GRAPH THEORY
[2]  
Bondy J.A., 2008, GRAD TEXTS MATH
[3]   Planar graph coloring avoiding monochromatic subgraphs:: Trees and paths make it difficult [J].
Broersma, H ;
Fomin, FV ;
Kratochvíl, J ;
Woeginger, GJ .
ALGORITHMICA, 2006, 44 (04) :343-361
[4]  
FLEISCHNER H., 1989, ANN DISCRETE MATH, V41, P171
[5]   NON-HAMILTONIAN BICUBIC GRAPHS [J].
GEORGES, JP .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 46 (01) :121-124
[6]   ON 2-FACTORS OF BIPARTITE REGULAR GRAPHS [J].
HORTON, JD .
DISCRETE MATHEMATICS, 1982, 41 (01) :35-41
[7]  
Jensen T. R., 1995, Graph Coloring Problems
[8]   Planar graph colorings without short monochromatic cycles [J].
Kaiser, T ;
Skrekovski, R .
JOURNAL OF GRAPH THEORY, 2004, 46 (01) :25-38
[9]   CUBIC BIPARTITE CYCLIC 4-CONNECTED GRAPHS WITHOUT HAMILTONIAN CIRCUITS [J].
KELMANS, AK .
RUSSIAN MATHEMATICAL SURVEYS, 1988, 43 (03) :205-206
[10]   HAMILTONIAN RESULTS IN K1,3 FREE GRAPHS [J].
MATTHEWS, MM ;
SUMNER, DP .
JOURNAL OF GRAPH THEORY, 1984, 8 (01) :139-146