Perfect divisibility and 2-divisibility

被引:26
作者
Chudnovsky, Maria [1 ]
Sivaraman, Vaidy [2 ]
机构
[1] Princeton Univ, Dept Math, Princeton, NJ 08544 USA
[2] SUNY Binghamton, Dept Math Sci, Binghamton, NY 13902 USA
基金
美国国家科学基金会;
关键词
2-divisibility; graph coloring; perfect divisibility; GRAPHS; BULL;
D O I
10.1002/jgt.22367
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A graph G is said to be 2-divisible if for all (nonempty) induced subgraphs H of G, V(H) can be partitioned into two sets A,B such that omega(A)<omega(H) and omega(B)<omega(H). (Here omega(G) denotes the clique number of G, the number of vertices in a largest clique of G). A graph G is said to be perfectly divisible if for all induced subgraphs H of G, V(H) can be partitioned into two sets A,B such that H[A] is perfect and omega(B)<omega(H). We prove that if a graph is (P5,C5)-free, then it is 2-divisible. We also prove that if a graph is bull-free and either odd-hole-free or P-5-free, then it is perfectly divisible.
引用
收藏
页码:54 / 60
页数:7
相关论文
共 10 条
[1]   Maximum Weight Independent Sets in Odd-Hole-Free Graphs Without Dart or Without Bull [J].
Brandstaedt, Andreas ;
Mosca, Raffaele .
GRAPHS AND COMBINATORICS, 2015, 31 (05) :1249-1262
[2]  
Chudnovsky M., 2017, SIAM J DISC MATH
[3]   The Erdos-Hajnal conjecture for bull-free graphs [J].
Chudnovsky, Maria ;
Safra, Shmuel .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (06) :1301-1310
[4]   The strong perfect graph theorem [J].
Chudnovsky, Maria ;
Robertson, Neil ;
Seymour, Paul ;
Thomas, Robin .
ANNALS OF MATHEMATICS, 2006, 164 (01) :51-229
[5]   On the structure of bull-free perfect graphs [J].
deFigueiredo, CMH ;
Maffray, F ;
Porto, O .
GRAPHS AND COMBINATORICS, 1997, 13 (01) :31-55
[6]  
Gy A., 1987, P INT C COMB AN ITS, V3, P413
[7]  
Hoang C. T., STRUCTURE BANN UNPUB
[8]   On the divisibility of graphs [J].
Hoàng, CT ;
McDiarmid, C .
DISCRETE MATHEMATICS, 2002, 242 (1-3) :145-156
[9]  
Lovasz L., 1972, Discrete Math., V2, P253, DOI DOI 10.1016/0012-365X(72)90006-4
[10]   RECOGNIZING BULL-FREE PERFECT GRAPHS [J].
REED, B ;
SBIHI, N .
GRAPHS AND COMBINATORICS, 1995, 11 (02) :171-178