3-colorability and forbidden subgraphs. I: Characterizing pairs

DOI10.1016/S0012-365X(03)00312-1zbMATH Open1031.05052MaRDI QIDQ1422435FDOQ1422435

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)

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?)
• Title not available (Why is that?)
• Graph Theory and Probability
• Sur le coloriage des graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• 25 pretty graph colouring problems
• Paw-free graphs
• Combinatorial Relations and Chromatic Graphs
• On the chromatic index of multigraphs without large triangles
• 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

Cited In (15)

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

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

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