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

DOI10.1007/978-3-540-69507-3_15MaRDI QIDQ5448772zbMATHOpenAlexFDO

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

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)

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

Cited in

(7)

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

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)