Non-perfect \((P_5, C_5, K_5 -e)\)-free graphs are 5-colorable

DOI10.1007/s00373-024-02866-6MaRDI QIDQ6660054

Yian Xu

Publication date: 10 January 2025

Published in: Graphs and Combinatorics (Search for Journal in Brave)

zbMATH Keywords

chromatic numberclique number\(P_5\)\(K_5 -e\)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Theory of computing (68Qxx) Enumerative combinatorics (05Axx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramsey-type theorems
• The strong perfect graph theorem
• \(K_{4}\)-free graphs with no odd holes
• Coloring the hypergraph of maximal cliques of a graph with no long path
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• The chromatic number of \(\{P_5,K_4\}\)-free graphs
• On the chromatic number of some \(P_5\)-free graphs
• Graph Theory and Probability
• Perfect coloring and linearly χ-boundP6-free graphs
• χ‐bounds, operations, and chords
• A survey of χ‐boundedness
• Perfect divisibility and 2‐divisibility
• Two cases of polynomial-time solvability for the coloring problem
• Polynomial bounds for chromatic number II: Excluding a star‐forest
• Coloring graphs without induced \(P_5\) or \(K_5-e\)
• Improved bounds on the chromatic number of (\(P_5\), flag)-free graphs
• The chromatic number of (\(P_5\), HVN)-free graphs

This page was built for publication: Non-perfect \((P_5, C_5, K_5 -e)\)-free graphs are 5-colorable