Coloring graphs with no induced five‐vertex path or gem
Maria Chudnovsky, T. Karthick, Peter Maceli, Frédéric Maffray
Abstract
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.
Topics & Concepts
CombinatoricsMathematicsVertex (graph theory)Induced pathClique numberNeighbourhood (mathematics)GraphDiscrete mathematicsWindmill graphChordal graphLongest path problemLine graphGraph powerMathematical analysisAdvanced Graph Theory ResearchGraph Labeling and Dimension ProblemsGraph theory and applications