Classes of graphs with no long cycle as a vertex-minor are polynomially chi-bounded
- Title
- Classes of graphs with no long cycle as a vertex-minor are polynomially chi-bounded
- Author
- 권오정
- Keywords
- Chromatic number; χ-bounded class; Vertex-minor; 1-join; Cycle
- Issue Date
- 2020-01
- Publisher
- ACADEMIC PRESS INC ELSEVIER SCIENCE
- Citation
- JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 140, page. 372-386
- Abstract
- 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.
- URI
- https://www.sciencedirect.com/science/article/pii/S0095895619300590?via%3Dihubhttps://repository.hanyang.ac.kr/handle/20.500.11754/169087
- ISSN
- 0095-8956; 1096-0902
- DOI
- 10.1016/j.jctb.2019.06.001
- Appears in Collections:
- COLLEGE OF NATURAL SCIENCES[S](자연과학대학) > MATHEMATICS(수학과) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML