pith. sign in

arxiv: 1512.03481 · v1 · pith:AQ3OXOO2new · submitted 2015-12-10 · 🧮 math.CO

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

classification 🧮 math.CO
keywords graphchromaticcliquecontainscycleeithereverygraphs
0
0 comments X
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.