Chi-boundedness of graph classes excluding wheel vertex-minors. (English) Zbl 1404.05201
Summary: A class of graphs is \(\chi\)-bounded if there exists a function \(f:\mathbb{N}\rightarrow\mathbb{N}\) such that for every graph \(G\) in the class and an induced subgraph \(H\) of \(G\), if \(H\) has no clique of size \(q+1\), then the chromatic number of \(H\) is less than or equal to \(f(q)\). We denote by \(W_n\) the wheel graph on \(n+1\) vertices. We show that the class of graphs having no vertex-minor isomorphic to \(W_n\) is \(\chi\)-bounded. This generalizes several previous results; \(\chi\)-boundedness for circle graphs, for graphs having no \(W_5\) vertex-minors, and for graphs having no fan vertex-minors.
MSC:
| 05C83 | Graph minors |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C75 | Structural characterization of families of graphs |
References:
| [1] | Bouchet, A., Isotropic systems, European J. Combin., 8, 3, 231-244 (1987) · Zbl 0642.05015 |
| [2] | Bouchet, A., Reducing prime graphs and recognizing circle graphs, Combinatorica, 7, 3, 243-254 (1987) · Zbl 0666.05037 |
| [3] | Bouchet, A., Graphic presentations of isotropic systems, J. Combin. Theory Ser. B, 45, 1, 58-76 (1988) · Zbl 0662.05014 |
| [4] | Bouchet, A., Connectivity of isotropic systems, (Combinatorial Mathematics: Proceedings of the Third International Conference. Combinatorial Mathematics: Proceedings of the Third International Conference, New York, 1985. Combinatorial Mathematics: Proceedings of the Third International Conference. Combinatorial Mathematics: Proceedings of the Third International Conference, New York, 1985, Ann. N.Y. Acad. Sci., vol. 555 (1989), New York Acad. Sci.: New York Acad. Sci. New York), 81-93 · Zbl 0741.05047 |
| [5] | Bouchet, A., \(κ\)-transformations, local complementations and switching, (Cycles and Rays. Cycles and Rays, Montreal, PQ, 1987. Cycles and Rays. Cycles and Rays, Montreal, PQ, 1987, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 301 (1990), Kluwer Acad. Publ.: Kluwer Acad. Publ. Dordrecht), 41-50 · Zbl 0718.05039 |
| [6] | Bouchet, A., Circle graph obstructions, J. Combin. Theory Ser. B, 60, 1, 107-144 (1994) · Zbl 0793.05116 |
| [7] | Choi, I.; Kwon, O.; Oum, S., Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors, J. Combin. Theory Ser. B, 123, 126-147 (2017) · Zbl 1354.05045 |
| [8] | Chudnovsky, M.; Scott, A.; Seymour, P., Induced subgraphs of graphs with large chromatic number. III. Long holes, Combinatorica, 37, 6, 1057-1072 (2017) · Zbl 1399.05068 |
| [9] | Diestel, R., Graph Theory, Graduate Texts in Mathematics, vol. 173 (2010), Springer: Springer Heidelberg · Zbl 1204.05001 |
| [10] | Dvořák, Z.; Král’, D., Classes of graphs with small rank decompositions are \(χ\)-bounded, European J. Combin., 33, 4, 679-683 (2012) · Zbl 1237.05072 |
| [11] | Geelen, J. F., Matchings, Matroids and Unimodular Matrices (1995), University of Waterloo, PhD thesis |
| [12] | Graham, R. L.; Rothschild, B. L.; Spencer, J. H., Ramsey Theory, Wiley-Interscience Series in Discrete Mathematics and Optimization (1990), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York, A Wiley-Interscience Publication · Zbl 0705.05061 |
| [13] | Gyárfás, A., On the chromatic number of multiple interval graphs and overlap graphs, Discrete Math., 55, 2, 161-166 (1985) · Zbl 0569.05019 |
| [14] | Gyárfás, A., Corrigendum: “On the chromatic number of multiple interval graphs and overlap graphs” [Discrete Math. 55 (1985), no. 2, 161-166; MR0798532 (86k:05052)], Discrete Math., 62, 3, 333 (1986) |
| [15] | Gyárfás, A., Problems from the world surrounding perfect graphs, Zastos. Mat., 19, 413-441 (1987) · Zbl 0718.05041 |
| [16] | Kwon, O.; Oum, S., Unavoidable vertex-minors in large prime graphs, European J. Combin., 41, 100-127 (2014) · Zbl 1300.05255 |
| [17] | Oum, S., Rank-width and vertex-minors, J. Combin. Theory Ser. B, 95, 1, 79-100 (2005) · Zbl 1070.05023 |
| [18] | Seidenberg, A., A simple proof of a theorem of Erdős and Szekeres, J. Lond. Math. Soc., 34, 352 (1959) · Zbl 0085.15003 |
| [19] | Trotter, W. T., Combinatorics and Partially Ordered Sets, Johns Hopkins Series in the Mathematical Sciences (1992), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD, Dimension theory · Zbl 0764.05001 |
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.
