Three complexity results on coloring P_k-free graphs

DOI10.1016/J.EJC.2011.12.008MaRDI QIDQ1933643zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Daniël Paulusma, Hajo Broersma, Petr A. Golovach

Publication date 24 January 2013

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2011.12.008

zbMATH Keywords

polynomial-time algorithmdominating cliquepre-colouring extensionpath free graphspolymial solvabilityvertex colouring problems

Mathematics Subject Classification ID

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

Recommendations

• Three complexity results on coloring \(P _{k }\)-free graphs
• Improved complexity results on \(k\)-coloring \(P _{t }\)-free graphs
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Updating the complexity status of coloring graphs without a fixed induced linear forest

Cited in

(33)

• Closing complexity gaps for coloring problems on \(H\)-free graphs
• 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs
• Choosability of P 5-Free Graphs
• Constructions of k-critical P₅-free graphs
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Acyclic, star, and injective colouring: bounding the diameter
• Colouring of (P₃ P₂)-free graphs
• 4-coloring \((P_6, \text{bull})\)-free graphs
• Certifying coloring algorithms for graphs without long induced paths
• List 3-coloring on comb-convex and caterpillar-convex bipartite graphs
• Complexity of \(C_k\)-coloring in hereditary classes of graphs
• Independent feedback vertex sets for graphs of bounded diameter
• A new characterization of P_k-free graphs
• Acyclic, star, and injective colouring: bounding the diameter
• On list \(k\)-coloring convex bipartite graphs
• Colouring \((P_r + P_s)\)-free graphs
• Three complexity results on coloring \(P _{k }\)-free graphs
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• 4-colorability of P₆-free graphs
• Colouring graphs of bounded diameter in the absence of small cycles
• Colouring graphs of bounded diameter in the absence of small cycles
• Colouring (P_r+P_s)-Free Graphs
• Partitioning \(H\)-free graphs of bounded diameter
• Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
• Complexity of coloring graphs without paths and cycles
• Improved complexity results on \(k\)-coloring \(P _{t }\)-free graphs
• 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles
• Complexity of coloring graphs without paths and cycles
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Two complexity results for the vertex coloring problem
• 3-colouring \(P_t\)-free graphs without short odd cycles
• On coloring a class of claw-free and hole-twin-free graphs

This page was built for publication: Three complexity results on coloring \(P_k\)-free graphs

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