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

dominating cliquepath free graphspolymial solvabilitypolynomial-time algorithmpre-colouring extensionvertex colouring problems

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Paths and cycles (05C38) 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

• 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

(34)

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