Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
classification
🧮 math.CO
keywords
graphchromaticcliquecontainscycleeithereverygraphs
read the original 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$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.