3-colorability and forbidden subgraphs. I: Characterizing pairs

DOI10.1016/S0012-365X(03)00312-1zbMath1031.05052MaRDI QIDQ1422435

Bert Randerath

Publication date: 14 February 2004

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

zbMATH Keywords

3-ColorabilityColoring algorithmsForbidden subgraphsVizing

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (14)

Vizing bound for the chromatic number on some graph classes ⋮ List coloring in the absence of two subgraphs ⋮ The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs. ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ Non-minimal degree-sequence-forcing triples ⋮ Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree ⋮ Coloring vertices of claw-free graphs in three colors ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ Colouring vertices of triangle-free graphs without forests ⋮ Minimal forbidden sets for degree sequence characterizations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the chromatic index of multigraphs without large triangles
• Paw-free graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Vertex colouring and forbidden subgraphs -- a survey
• On a property of the class of n-colorable graphs
• Graph Theory and Probability
• Sur le coloriage des graphs
• Combinatorial Relations and Chromatic Graphs
• 25 pretty graph colouring problems

This page was built for publication: 3-colorability and forbidden subgraphs. I: Characterizing pairs