Coloring graphs with no induced subdivision of K₄^+
classification
🧮 math.CO
keywords
graphedgeinducednumbersubdivisionverticeschromaticclique
read the original abstract
Let $K_4^+$ be the 5-vertex graph obtained from $K_4$, the complete graph on four vertices, by subdividing one edge precisely once (i.e. by replacing one edge by a path on three vertices). We prove that if the chromatic number of some graph $G$ is much larger than its clique number, then $G$ contains a subdivision of $K_4^+$ as an induced subgraph.
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.