The chromatic number of (P₅, K₅-e)-free graphs

2022/10/10 by Yian Xu, Xu, Yian
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2210.04682

openalex publication_date 2022/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G be a graph. We use χ(G) and ω(G) to denote the chromatic number and clique number of G respectively. A P₅ is a path on 5 vertices. A family of graphs G is said to be \itχ-bounded if there exists some function f such that χ(G)≤ f(ω(G)) for every G\inG. In this paper, we show that the family of (P₅, K₅-e)-free graphs is χ-bounded by a linear function: χ(G)≤ max\13,ω(G)+1\.

Related

• The chromatic number of (P₅, HVN )-free graphs
• Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path
• On graphs with no induced P₅ or K₅-e
• On the chromatic number of some (P₃∪ P₂)-free graphs
• A tight linear bound to the chromatic number of (P₅, K₁+(K₁∪ K₃))-free graphs