A class of graphs is χ-bounded if there exists a function f:N→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 Wn the wheel graph on n+1 vertices. We show that the class of graphs having no vertex-minor isomorphic to Wn is χ-bounded. This generalizes several previous results; χ-boundedness for circle graphs, for graphs having no W5 vertex-minors, and for graphs having no fan vertex-minors.
Chi-boundedness of graph classes excluding wheel vertex-minors / Choi, H.; Kwon, O. -J.; Oum, S. -I.; Wollan, P.. - In: JOURNAL OF COMBINATORIAL THEORY. - ISSN 0095-8956. - 135:(2019), pp. 319-348. [10.1016/j.jctb.2018.08.009]
Chi-boundedness of graph classes excluding wheel vertex-minors
Wollan P.
2019
Abstract
A class of graphs is χ-bounded if there exists a function f:N→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 Wn the wheel graph on n+1 vertices. We show that the class of graphs having no vertex-minor isomorphic to Wn is χ-bounded. This generalizes several previous results; χ-boundedness for circle graphs, for graphs having no W5 vertex-minors, and for graphs having no fan vertex-minors.| File | Dimensione | Formato | |
|---|---|---|---|
|
Choi_Chi-boundedness_2019.pdf
Open Access dal 12/09/2020
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Creative commons
Dimensione
318.78 kB
Formato
Adobe PDF
|
318.78 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
