Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors

A fan F-k is a graph that consists of an induced path on k vertices and an additional vertex that is adjacent to all vertices of the path. We prove that for all positive integers q and k, every graph with sufficiently large chromatic number contains either a clique of size q or a vertex-minor isomorphic to F-k. We also prove that for all positive integers q and k >= 3, every graph with sufficiently large chromatic number contains either a clique of size q or a pivot-minor isomorphic to a cycle of length k. (C) 2016 Elsevier Inc. All rights reserved.
Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
Issue Date
2017-03
Language
English
Keywords

LARGE CHROMATIC NUMBER; RANK-WIDTH; CIRCLE GRAPH; ISOTROPIC SYSTEMS; INDUCED SUBGRAPHS; TREES; OBSTRUCTIONS; BIPARTITE

Citation

JOURNAL OF COMBINATORIAL THEORY SERIES B, v.123, pp.126 - 147

ISSN
0095-8956
DOI
10.1016/j.jctb.2016.11.007
URI
http://hdl.handle.net/10203/220433
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
  • Hit : 103
  • Download : 0
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0