Classes of graphs with no long cycle as a vertex-minor are polynomially chi-bounded

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 106
  • Download : 0
A class g of graphs is chi-bounded if there is a function f such that for every graph G is an element of g and every induced subgraph H of G, chi(H) <= f (omega(H)). In addition, we say that G is polynomially chi-bounded if f can be taken as a polynomial function. We prove that for every integer n >= 3, there exists a polynomial f such that chi(H) <= f (omega(H)) for all graphs with no vertex-minor isomorphic to the cycle graph C-n. To prove this, we show that if G is polynomially chi-bounded, then so is the closure of g under taking the 1-join operation. (C) 2019 Elsevier Inc. All rights reserved.
Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
Issue Date
2020-01
Language
English
Article Type
Article
Citation

JOURNAL OF COMBINATORIAL THEORY SERIES B, v.140, pp.372 - 386

ISSN
0095-8956
DOI
10.1016/j.jctb.2019.06.001
URI
http://hdl.handle.net/10203/270914
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