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

DOI10.1007/978-3-540-69507-3_15MaRDI QIDQ5448772zbMATH OpenOpenAlexFDO

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

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

Recommendations

• Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
• -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)

• -backbone colorings along pairwise disjoint stars and matchings
• Optimal backbone coloring of split graphs with matching backbones
• Backbone coloring for triangle-free planar graphs
• The \(\lambda\)-backbone colorings of graphs with tree backbones
• 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
• On \(\lambda\)-backbone coloring of cliques with tree backbones in linear time

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)