Optimal chromatic bound for (P₃∪ P₂, house)-free graphs

2023/08/10 by Rui Li, Di Wu, Li, Rui +3
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.2308.05442

openalex publication_date 2023/08/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G and H be two vertex disjoint graphs. The \em union G∪ H is the graph with V(G∪ H)=V(G)∪ V(H) and E(G∪ H)=E(G)∪ E(H). We use P_k to denote a \em path on k vertices, use \em house to denote the complement of P₅. In this paper, we show that χ(G)≤2ω(G) if G is (P₃∪ P₂, house)-free. Moreover, this bound is optimal when ω(G)≥2.

Related

• A tight linear chromatic bound for (P₃∪ P₂, W₄)-free graphs
• A tight linear bound to the chromatic number of (P₅, K₁+(K₁∪ K₃))-free graphs
• Optimal chromatic bound for (P₂∪ P₄, HVN)-free graphs
• Optimal chromatic bound for (P₂+P₃, P₂+ P₃)-free graphs
• Tight Chromatic Upper Bound for 3 Times K1, 2 Times K1 + (K2 UNION K1)-free Graphs