Coloring graphs with no induced five‐vertex path or gem
Maria Chudnovsky, T. Karthick, Peter Maceli, Frédéric Maffray · Journal of Graph Theory · 2020
Abstract For a graph , let and , respectively, denote the chromatic number and clique number of . We give an explicit structural description of (, gem)‐free graphs, and show that every such graph satisfies . Moreover, this bound is best possible. Here a gem is the graph that consists of an induced four‐vertex path plus a vertex which is adjacent to all the vertices of that path.