BROWSE

Related Scientist

Researcher

엄상일
수리 및 계산 과학 연구단
more info

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

Cited 0 time in webofscience Cited 0 time in scopus
23 Viewed 3 Downloaded
Title
Classes of graphs with no long cycle as a vertex-minor are polynomially χ-bounded
Author(s)
Kim R.; Kwon O.-J.; Sang-il Oum; Sivaraman V.
Publication Date
2020-01
Journal
JOURNAL OF COMBINATORIAL THEORY SERIES B, v.140, no., pp.372 - 386
Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
Abstract
© 2019 Elsevier Inc.A class G of graphs is χ-bounded if there is a function f such that for every graph G∈G and every induced subgraph H of G, χ(H)⩽f(ω(H)). In addition, we say that G is polynomially χ-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 χ(G)⩽f(ω(G)) for all graphs with no vertex-minor isomorphic to the cycle graph Cn. To prove this, we show that if G is polynomially χ-bounded, then so is the closure of G under taking the 1-join operation
URI
https://pr.ibs.re.kr/handle/8788114/6682
ISSN
0095-8956
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > Journal Papers (저널논문)
Files in This Item:
Classes of graphs with no long cycle as a vertex-minor are polynomially χ-bounded.pdfDownload

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse