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

Abstract

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\ge 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$.

19 pages, 5 figures

References in corpus (1)

• Excluded vertex-minors for graphs of linear rank-width at most k

Cited by in corpus (2)

• Classes of graphs with no long cycle as a vertex-minor are polynomially $\chi$-bounded
• Chi-boundedness of graph classes excluding wheel vertex-minors