3-colorability and forbidden subgraphs. I: Characterizing pairs

DOI10.1016/S0012-365X(03)00312-1MaRDI QIDQ1422435zbMATH OpenFDO

Authors 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)

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

Cites work

• scientific article; zbMATH DE number 3747156 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• scientific article; zbMATH DE number 1833071 (Why is no real title available?)
• scientific article; zbMATH DE number 3286813 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• 25 pretty graph colouring problems
• Combinatorial Relations and Chromatic Graphs
• Graph Theory and Probability
• On a property of the class of n-colorable graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• On the chromatic index of multigraphs without large triangles
• Paw-free graphs
• Sur le coloriage des graphs
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Vertex colouring and forbidden subgraphs -- a survey

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
• Non-minimal degree-sequence-forcing triples
• A characterization of small 3-colorable graphs

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)