3-colorability $\in \mathcal P$ for $P_{6}$-free graphs.

DOI10.1016/S0166-218X(03)00446-3zbMath1035.05042OpenAlexW1509433326MaRDI QIDQ1427186

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-Colorability Perfect graphs Coloring algorithms Graph classes

Mathematics Subject Classification ID

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

Related Items (58)

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

Cites Work

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

3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.