3-colorability and forbidden subgraphs. I: Characterizing pairs

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

Authors: Bert Randerath 

Publication date: 14 February 2004

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

Recommendations

• 3-colourability and forbidden subgraphs
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Coloring graphs characterized by a forbidden subgraph
• On the chromatic number of a graph with two forbidden subgraphs

zbMATH Keywords

3-ColorabilityColoring algorithmsForbidden subgraphsVizing

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

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

Cited In (19)

• Colouring of graphs with Ramsey-type forbidden subgraphs
• Coloring vertices of claw-free graphs in three colors
• Colouring vertices of triangle-free graphs without forests
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Forbidden subgraphs and 3-colorings
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• 3-colourability and forbidden subgraphs
• Colouring vertices of triangle-free graphs
• On the chromatic number of a graph with two 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
• Forbidden triples generating a finite set of graphs with minimum degree three
• Clique-width of graph classes defined by two forbidden induced subgraphs
• Minimal forbidden sets for degree sequence characterizations
• Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree
• A characterization of small 3-colorable graphs
• 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)