Improved Upper Bounds for λ-Backbone Colorings Along Matchings and Stars

DOI10.1007/978-3-540-69507-3_15zbMATH Open1131.05301OpenAlexW2149362867MaRDI QIDQ5448772FDOQ5448772

Authors: Bert Marchal, Daniël Paulusma, A. N. M. Salman, Hajo Broersma 

Publication date: 7 March 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69507-3_15

Recommendations

• Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
• \(\lambda \)-backbone colorings along pairwise disjoint stars and matchings
• The \(\lambda\)-backbone colorings of graphs with tree backbones
• Optimal backbone coloring of split graphs with matching backbones
• Backbone colorings of graphs with bounded degree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (5)

• The \(\lambda\)-backbone colorings of graphs with tree backbones
• \(\lambda \)-backbone colorings along pairwise disjoint stars and matchings
• Backbone coloring for triangle-free planar graphs
• The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
• Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number

This page was built for publication: Improved Upper Bounds for λ-Backbone Colorings Along Matchings and Stars

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