3-colorability P for P₆-free graphs.

DOI10.1016/S0166-218X(03)00446-3zbMATH Open1035.05042OpenAlexW1509433326MaRDI QIDQ1427186FDOQ1427186

Bert Randerath, Ingo Schiermeyer

Publication date: 14 March 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00446-3

zbMATH Keywords

3-ColorabilityPerfect graphsColoring algorithmsGraph classes

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph Theory and Probability
• The complexity of colouring problems on dense graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• The NP-Completeness of Edge-Coloring
• The complexity of theorem-proving procedures
• The strong perfect graph theorem
• Dominating cliques in \(P_ 5\)-free graphs
• The complexity of coloring graphs without long induced paths
• Coloring perfect \((K_ 4\)-e)-free graphs
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Vertex colouring and forbidden subgraphs -- a survey
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• 3-colorability and forbidden subgraphs. I: Characterizing pairs
• A reduction procedure for coloring perfect \(K_ 4\)-free graphs
• Chromatic number of graphs each path of which is 3-colourable
• Colouring Graphs with Prescribed Induced Cycle Lengths

Cited In (59)

• 3-colouring \(P_t\)-free graphs without short odd cycles
• A New Characterization of P 6-Free Graphs
• On the parameterized complexity of coloring graphs in the absence of a linear forest
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Finding a dominating set on bipartite graphs
• Coloring vertices of claw-free graphs in three colors
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Choosability of P 5-Free Graphs
• Constructions of \(k\)-critical \(P_5\)-free graphs
• Vertex coloring of graphs with few obstructions
• Colouring vertices of triangle-free graphs without forests
• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• Coloring graphs without short cycles and long induced paths
• On the complexity of 4-coloring graphs without long induced paths
• Independent feedback vertex set for \(P_5\)-free graphs
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Coloring Graphs without Short Cycles and Long Induced Paths
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Efficiency in exponential time for domination-type problems
• Colouring of \((P_3 \cup P_2)\)-free graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• 4-coloring \((P_6, \text{bull})\)-free graphs
• On the chromatic number of (\(P_6\), diamond)-free graphs
• Membrane computing to enhance time efficiency of minimum dominating set
• Stable sets in \(k\)-colorable \(P_{5}\)-free graphs
• On two techniques of combining branching and treewidth
• A new characterization of \(P_k\)-free graphs
• A Note on k-Colorability of P 5-Free Graphs
• Colouring \((P_r + P_s)\)-free graphs
• List coloring in the absence of a linear forest
• 3-Colorable Subclasses of $P_8$-Free Graphs
• 3-colouring AT-free graphs in polynomial time
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Partitioning graphs into connected parts
• A new characterization of \(P_{6}\)-free graphs
• Vizing bound for the chromatic number on some graph classes
• Partitioning Graphs into Connected Parts
• 4-colorability of \(P_6\)-free graphs
• A Faster Algorithm for Dominating Set Analyzed by the Potential Method
• Colouring (P_r+P_s)-Free Graphs
• On indicated coloring of some classes of graphs
• NP-hard graph problems and boundary classes of graphs
• An exact algorithm for the minimum dominating clique problem
• Critical \((P_6, \mathrm{banner})\)-free graphs
• List Coloring in the Absence of a Linear Forest
• Perfect matching cuts partitioning a graph into complementary subgraphs
• Complexity of coloring graphs without paths and cycles
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
• Connected greedy coloring of \(H\)-free graphs
• Solving connected dominating set faster than \(2^n\)
• 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles
• Colouring Vertices of Triangle-Free Graphs
• Pathwidth of cubic graphs and exact algorithms
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs
• 4-Coloring H-Free Graphs When H Is Small

This page was built for publication: 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.

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