Article ID Journal Published Year Pages File Type
5777634 Journal of Combinatorial Theory, Series B 2017 22 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,