Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777634 | Journal of Combinatorial Theory, Series B | 2017 | 22 Pages |
Abstract
A fan Fk 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 Fk. 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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ilkyoo Choi, O-joung Kwon, Sang-il Oum,