Coloring graphs with no induced subdivision of K₄^+

Publication date 14 January 2019

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 page was built for publication: Coloring graphs with no induced subdivision of $K_4^+$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6312425)