A survey of χ-boundedness

被引：110
作者：
Scott, Alex [1 ]
Seymour, Paul [2 ]
机构：
[1] Univ Oxford, Math Inst, Oxford OX2 6GG, England
[2] Princeton Univ, Dept Math, Princeton, NJ 08544 USA
来源：
JOURNAL OF GRAPH THEORY | 2020年 / 95卷 / 03期
关键词：
chi-boundedness; colouring; ARCWISE CONNECTED SETS; CHROMATIC NUMBER; INDUCED SUBGRAPHS; INTERSECTION GRAPHS; BOUNDS; TREES; CYCLE; HYPERGRAPH; CONJECTURE; PATTERNS;
D O I：
10.1002/jgt.22601
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
If a graph has bounded clique number and sufficiently large chromatic number, what can we say about its induced subgraphs? Andras Gyarfas made a number of challenging conjectures about this in the early 1980s, which have remained open until recently; but in the last few years there has been substantial progress. This is a survey of where we are now.
引用
收藏
页码：473 / 504
页数：32
相关论文
共 122 条
[1]   -bounded families of oriented graphs [J].
Aboulker, P. ;
Bang-Jensen, J. ;
Bousquet, N. ;
Charbit, P. ;
Havet, F. ;
Maffray, F. ;
Zamora, J. .
JOURNAL OF GRAPH THEORY, 2018, 89 (03) :304-326
[2]   Excluding 4-Wheels [J].
Aboulker, Pierre .
JOURNAL OF GRAPH THEORY, 2014, 75 (04) :311-322
[3]   GRAPHS THAT DO NOT CONTAIN A CYCLE WITH A NODE THAT HAS AT LEAST TWO NEIGHBORS ON IT [J].
Aboulker, Pierre ;
Radovanovic, Marko ;
Trotignon, Nicolas ;
Vuskovic, Kristina .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (04) :1510-1531
[4]   Bisimplicial vertices in even-hole-free graphs [J].
Addario-Berry, Louigi ;
Chudnovsky, Maria ;
Havet, Frederic ;
Reed, Bruce ;
Seymour, Paul .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (06) :1119-1164
[5]   Bisimplicial vertices in even-hole-free graphs (vol 98, pg 1119, 2008) [J].
Addario-Berry, Louigi ;
Chudnovsky, Maria ;
Havet, Frederic ;
Reed, Bruce ;
Seymour, Paul .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 142 :374-375
[6]   Crossing patterns of semi-algebraic sets [J].
Alon, N ;
Pach, J ;
Pinchasi, R ;
Radoicic, R ;
Sharir, M .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2005, 111 (02) :310-326
[7]   SUBGRAPHS OF LARGE CONNECTIVITY AND CHROMATIC NUMBER IN GRAPHS OF LARGE CHROMATIC NUMBER [J].
ALON, N ;
KLEITMAN, D ;
THOMASSEN, C ;
SAKS, M ;
SEYMOUR, P .
JOURNAL OF GRAPH THEORY, 1987, 11 (03) :367-371
[8]  
Alon N., 1994, the electronic journal of combinatorics, V1, pR12
[9]   Coloring, sparseness and girth [J].
Alon, Noga ;
Kostochka, Alexandr ;
Reiniger, Benjamin ;
West, Douglas B. ;
Zhu, Xuding .
ISRAEL JOURNAL OF MATHEMATICS, 2016, 214 (01) :315-331
[10]  
Asplund E., 1960, Mathematica Scandinavica, V8, P181, DOI DOI 10.7146/MATH.SCAND.A-10607
12345678910