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

DOI10.1007/978-3-540-69507-3_15zbMath1131.05301OpenAlexW2149362867MaRDI QIDQ5448772

Bert Marchal, Daniël Paulusma, A. N. M. Salman, Hajo J. 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 theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Backbone coloring for triangle-free planar graphs, The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones, \(\lambda \)-backbone colorings along pairwise disjoint stars and matchings