×

Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi\)-bounded. (English) Zbl 1430.05058

Summary: A class \(\mathcal{G}\) of graphs is \(\chi\)-bounded if there is a function \(f\) such that for every graph \(G \in \mathcal{G}\) and every induced subgraph \(H\) of \(G\), \(\chi(H) \leqslant f(\omega(H))\). In addition, we say that \(\mathcal{G}\) is polynomially \(\chi\)-bounded if \(f\) can be taken as a polynomial function. We prove that for every integer \(n \geqslant 3\), there exists a polynomial \(f\) such that \(\chi(G) \leqslant f(\omega(G))\) for all graphs with no vertex-minor isomorphic to the cycle graph \(C_n\). To prove this, we show that if \(\mathcal{G}\) is polynomially \(\chi \)-bounded, then so is the closure of \(\mathcal{G}\) under taking the 1-join operation.

MSC:

05C31 Graph polynomials
05C76 Graph operations (line graphs, products, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Choi, Hojin; Kwon, O-joung; Oum, Sang-il; Wollan, Paul, Chi-boundedness of graph classes excluding wheel vertex-minors, J. Combin. Theory Ser. B, 135, 319-348 (2019) · Zbl 1404.05201
[2] Choi, Ilkyoo; Kwon, O-joung; Oum, Sang-il, Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors, J. Combin. Theory Ser. B, 123, 126-147 (2017) · Zbl 1354.05045
[3] Chudnovsky, Maria; Oum, Sang-il, Vertex-minors and the Erdős-Hajnal conjecture, Discrete Math., 341, 12, 3498-3499 (2018) · Zbl 1397.05182
[4] Chudnovsky, Maria; Penev, Irena; Scott, Alex; Trotignon, Nicolas, Substitution and χ-boundedness, J. Combin. Theory Ser. B, 103, 5, 567-586 (2013), MR 3096332 · Zbl 1301.05230
[5] Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin, The strong perfect graph theorem, Ann. of Math. (2), 164, 1, 51-229 (2006), MR 2233847 (2007c:05091) · Zbl 1112.05042
[6] Chudnovsky, Maria; Scott, Alex; Seymour, Paul, Induced subgraphs of graphs with large chromatic number. III. Long holes, Combinatorica, 37, 6, 1057-1072 (2017), MR 3759907 · Zbl 1399.05068
[7] Dvořák, Zdeněk; Král, Daniel, Classes of graphs with small rank decompositions are χ-bounded, European J. Combin., 33, 4, 679-683 (2012), MR 3350076 · Zbl 1237.05072
[8] Esperet, Louis; Lemoine, Laetitia; Maffray, Frédéric; Morel, Grégory, The chromatic number of \(\{P_5, K_4 \}\)-free graphs, Discrete Math., 313, 6, 743-754 (2013), MR 3010736 · Zbl 1260.05056
[9] Gyárfás, András, Problems from the world surrounding perfect graphs, Zastos. Mat., 19, 413-441 (1987) · Zbl 0718.05041
[10] Karthick, T.; Maffray, Frédéric, Vizing bound for the chromatic number on some graph classes, Graphs Combin., 32, 4, 1447-1460 (2016), MR 3514976 · Zbl 1342.05040
[11] Kim, Ringi, Chromatic Number, Clique Number and n-Join of Graphs (2011), Master’s thesis, KAIST
[12] Kwon, O-joung; Oum, Sang-il, Unavoidable vertex-minors in large prime graphs, European J. Combin., 41, 100-127 (2014), MR 3219254 · Zbl 1300.05255
[13] Schiermeyer, Ingo, Chromatic number of \(P_5\)-free graphs: Reed’s conjecture, Discrete Math., 339, 7, 1940-1943 (2016), MR 3488929 · Zbl 1334.05045
[14] Scott, Alex; Seymour, Paul, A survey on χ-boundedness (2018) · Zbl 1486.05102
[15] Spencer, Joel, Ramsey’s theorem—a new lower bound, J. Combin. Theory Ser. A, 18, 108-115 (1975), MR 0366726 · Zbl 0296.05003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.