Three-colourability and forbidden subgraphs. II: Polynomial algorithms
From MaRDI portal
Publication:1613477
DOI10.1016/S0012-365X(01)00335-1zbMath0999.05042OpenAlexW1979630335WikidataQ55920244 ScholiaQ55920244MaRDI QIDQ1613477
Meike Tewes, Bert Randerath, Ingo Schiermeyer
Publication date: 29 August 2002
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0012-365x(01)00335-1
Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (32)
Triangle-free graphs and forbidden subgraphs ⋮ Colouring graphs with no induced six-vertex path or diamond ⋮ Triangle-free graphs with no six-vertex induced path ⋮ Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time ⋮ 4-colorability of \(P_6\)-free graphs ⋮ The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices ⋮ Complexity classification of the edge coloring problem for a family of graph classes ⋮ Colouring \((P_r + P_s)\)-free graphs ⋮ On the chromatic number of (\(P_6\), diamond)-free graphs ⋮ An optimal χ‐bound for (P6, diamond)‐free graphs ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Optimal chromatic bound for (P2+P3,P2+P3¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graphs ⋮ 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ 3-colorability and forbidden subgraphs. I: Characterizing pairs ⋮ Better 3-coloring algorithms: excluding a triangle and a seven vertex path ⋮ 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs. ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ NP-hard graph problems and boundary classes of graphs ⋮ On the complexity of 4-coloring graphs without long induced paths ⋮ Coloring vertices of claw-free graphs in three colors ⋮ First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ Three-coloring and list three-coloring of graphs without induced paths on seven vertices ⋮ Obstructions for three-coloring graphs without induced paths on six vertices ⋮ Colouring (P_r+P_s)-Free Graphs ⋮ On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets ⋮ Colouring graphs with no induced six-vertex path or diamond ⋮ Colouring vertices of triangle-free graphs without forests ⋮ Independent Feedback Vertex Set for P_5-free Graphs ⋮ The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
This page was built for publication: Three-colourability and forbidden subgraphs. II: Polynomial algorithms
