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

DOI10.1007/978-3-540-85238-4_31MaRDI QIDQ3599143zbMATH OpenOpenAlexFDO

Authors Marcin Kamiński, Joe Sawada, Xiao Shu, Chính T. Hoàng, Vadim 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

\(P _{5}\)-free graphsdominating cliquegraph coloring

Mathematics Subject Classification ID

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

Recommendations

• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Stable sets in \(k\)-colorable \(P_{5}\)-free graphs
• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• On 3-colorable P₅-free graphs
• Three complexity results on coloring \(P _{k }\)-free graphs

Cites work

• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Dominating cliques in \(P_ 5\)-free graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• scientific article; zbMATH DE number 1455118 (Why is no real title available?)
• On the complexity of 4-coloring graphs without long induced paths
• Optimizing weakly triangulated graphs
• Permutation Graphs and Transitive Graphs
• Reducibility among combinatorial problems
• Some simplified NP-complete graph problems
• The complexity of coloring graphs without long induced paths
• The ellipsoid method and its consequences in combinatorial optimization
• Topics on perfect graphs

Cited in

(18)

• \(K_ 5\) is the only double-critical 5-chromatic graph
• The total coloring of \(K_5\)-minor-free graphs
• Constructions of k-critical P₅-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
• Choosability of P 5-Free Graphs
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• A (5,5)-Colouring of K_n with Few Colours
• On 3-colorable P₅-free graphs
• scientific article; zbMATH DE number 6604949 (Why is no real title available?)
• On the chromatic number of \(P_5\)-free graphs with no large intersecting cliques
• On cd-coloring of \(\{P_5,K_4\}\)-free chordal graphs
• On the chromatic number of (P5,dart)-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Coloring algorithms for \(K_ 5\)-minor free graphs
• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
• Stable sets in \(k\)-colorable \(P_{5}\)-free graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3599143)