Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph

被引:0
作者
Nguyen, Tung [1 ]
Scott, Alex [2 ]
Seymour, Paul [1 ]
机构
[1] Princeton Univ, Princeton, NJ USA
[2] Univ Oxford, Math Inst, Oxford OX2 6GG, England
基金
美国国家科学基金会; 英国工程与自然科学研究理事会;
关键词
chromatic number; induced subgraphs;
D O I
10.1002/jgt.23129
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We prove that for every path H $H$, and every integer d $d$, there is a polynomial f $f$ such that every graph G $G$ with chromatic number greater than f( t ) $f(t)$ either contains H $H$ as an induced subgraph, or contains as a subgraph the complete d $d$-partite graph with parts of cardinality t $t$. For t = 1 $t=1$ and general d $d$ this is a classical theorem of Gy & aacute;rf & aacute;s, and for d = 2 $d=2$ and general t $t$ this is a theorem of Bonamy et al.
引用
收藏
页码:509 / 521
页数:13
相关论文
共 20 条
[1]   Degeneracy of Pt-free and C≥t-free graphs with no large complete bipartite subgraphs [J].
Bonamy, Marthe ;
Bousquet, Nicolas ;
Pilipczuk, Michal ;
Rzazewski, Pawel ;
Thomasse, Stephan ;
Walczak, Bartosz .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2022, 152 :353-378
[2]   Polynomial bounds for chromatic number VI. Adding a four-vertex path [J].
Chudnovsky, Maria ;
Scott, Alex ;
Seymour, Paul ;
Spirkl, Sophie .
EUROPEAN JOURNAL OF COMBINATORICS, 2023, 110
[3]   Excluding pairs of graphs [J].
Chudnovsky, Maria ;
Scott, Alex ;
Seymour, Paul .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2014, 106 :15-29
[4]  
Esperet L., 2017, THESIS U GRENOBLE AL, P24
[5]   Subgraphs of large connectivity and chromatic number [J].
Girao, Antonio ;
Narayanan, Bhargav .
BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 2022, 54 (03) :868-875
[6]  
Gyarfas A., 1985, ZASTOWANIA MATEMATYK, VXIX, P413, DOI DOI 10.4064/AM-19-3-4-413-441
[7]  
Gyrfs A., 1975, INFINITE FINITE SETS, V10, P801
[8]   RADIUS 2 TREES SPECIFY CHI-BOUNDED CLASSES [J].
KIERSTEAD, HA ;
PENRICE, SG .
JOURNAL OF GRAPH THEORY, 1994, 18 (02) :119-129
[9]   Applications of hypergraph coloring to coloring graphs not inducing certain trees [J].
Kierstead, HA ;
Rodl, V .
DISCRETE MATHEMATICS, 1996, 150 (1-3) :187-193
[10]   HIGHLY CONNECTED SUBGRAPHS WITH LARGE CHROMATIC NUMBER [J].
Nguyen, Tung H. .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2024, 38 (01) :243-260