Brooks' theorem for generalized dart graphs

DOI10.1016/J.IPL.2011.11.010MaRDI QIDQ413285zbMATH OpenOpenAlexFDO

Authors Martin Kochol, Riste Škrekovski

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

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)

Recommendations

• scientific article; zbMATH DE number 125481
• 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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1833071 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• A characterisation of some 2-connected graphs and a comment on an algorithmic proof of Brooks' theorem
• Some simplified NP-complete graph problems
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• Three short proofs in graph theory
• Δ-List Vertex Coloring in Linear Time

Cited in

(14)

• Degree‐bounded coloring of graphs: Variations on a theme by brooks
• Brooks' theorem with forbidden colors
• Brook's theorem
• Brooks' theorem on powers of graphs
• A note on a Brooks' type theorem for DP-coloring
• A matroid analogue of a theorem of Brooks for graphs
• A note on graph coloring extensions and list-colorings
• Dichotomy for coloring of dart graphs
• A Brooks-like result for graph powers
• A unified proof of Brooks' theorem and Catlin's theorem
• About a Brooks-type theorem for improper colouring
• A Brooks-type theorem for the bichromatic number
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems
• BROOKS’ THEOREM FOR MEASURABLE COLORINGS

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)