Chi-boundedness of graph classes excluding wheel vertex-minors

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 65
  • Download : 0
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. © 2017 Elsevier B.V.
Publisher
Elsevier B.V.
Issue Date
2017-08
Language
English
Article Type
Article
Citation

Electronic Notes in Discrete Mathematics, v.61, pp.247 - 253

ISSN
1571-0653
DOI
10.1016/j.endm.2017.06.045
URI
http://hdl.handle.net/10203/244086
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0