A Note on k-Colorability of P 5-Free Graphs

DOI10.1007/978-3-540-85238-4_31zbMath1173.05351OpenAlexW1967357793MaRDI QIDQ3599143

Marcin Kaminski, Joe Sawada, Xiao Shu, Chính T. Hoàng, Vadim V. Lozin

Publication date: 3 February 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85238-4_31

zbMATH Keywords

graph coloringdominating clique\(P _{5}\)-free graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Choosability of P 5-Free Graphs ⋮ On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs ⋮ Constructions of \(k\)-critical \(P_5\)-free graphs ⋮ Stable sets in \(k\)-colorable \(P_{5}\)-free graphs ⋮ Domination, coloring and stability in \(P_5\)-reducible graphs ⋮ Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Topics on perfect graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Dominating cliques in \(P_ 5\)-free graphs
• Some simplified NP-complete graph problems
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Optimizing weakly triangulated graphs
• On the complexity of 4-coloring graphs without long induced paths
• Reducibility among Combinatorial Problems
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Permutation Graphs and Transitive Graphs

This page was built for publication: A Note on k-Colorability of P 5-Free Graphs