Three complexity results on coloring P_k-free graphs
DOI10.1016/J.EJC.2011.12.008zbMATH Open1257.05037OpenAlexW2159829425WikidataQ60488525 ScholiaQ60488525MaRDI QIDQ1933643FDOQ1933643
Daniël Paulusma, Fedor V. Fomin, 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
polynomial-time algorithmdominating cliquepre-colouring extensionpath free graphspolymial solvabilityvertex colouring problems
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)
Cited In (27)
- 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Constructions of \(k\)-critical \(P_5\)-free graphs
- Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
- Acyclic, star, and injective colouring: bounding the diameter
- Colouring of \((P_3 \cup P_2)\)-free graphs
- List 3-coloring on comb-convex and caterpillar-convex bipartite graphs
- 4-coloring \((P_6, \text{bull})\)-free graphs
- Certifying coloring algorithms for graphs without long induced paths
- Independent feedback vertex sets for graphs of bounded diameter
- Acyclic, star, and injective colouring: bounding the diameter
- A new characterization of \(P_k\)-free graphs
- On list \(k\)-coloring convex bipartite graphs
- Colouring \((P_r + P_s)\)-free graphs
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Colouring graphs of bounded diameter in the absence of small cycles
- Colouring graphs of bounded diameter in the absence of small cycles
- 4-colorability of \(P_6\)-free graphs
- 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
- 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐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
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 👍 👎
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)
