Brooks' theorem for generalized dart graphs

DOI10.1016/J.IPL.2011.11.010zbMATH Open1239.05070OpenAlexW2080337943MaRDI QIDQ413285FDOQ413285

Riste Škrekovski, Martin Kochol

Publication date: 4 May 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.11.010

Recommendations

• scientific article
• The colour theorems of Brooks and Gallai extended
• An analog of Brooks' theorem for dynamic colorings
• Dichotomy for coloring of dart graphs
• Brooks' theorem on powers of graphs

zbMATH Keywords

graph algorithmsBrooks' theoremNP-complete problem(ks)-dart graphs)-diamond

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex degrees (05C07) 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?)
• Some simplified NP-complete graph problems
• Three short proofs in graph theory
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• Title not available (Why is that?)
• A characterisation of some 2-connected graphs and a comment on an algorithmic proof of Brooks' theorem
• Δ-List Vertex Coloring in Linear Time

Cited In (5)

• Brooks' theorem on powers of graphs
• A note on graph coloring extensions and list-colorings
• About a Brooks-type theorem for improper colouring
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems
• Degree‐bounded coloring of graphs: Variations on a theme by brooks

This page was built for publication: Brooks' theorem for generalized dart graphs

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