Search
Abstract
Let G be a simple graph, H be its spanning subgraph and λ≥2 be an integer. By a λ -backbone coloring of G with backbone H we mean any function c that assigns positive integers to vertices of G in such a way that |c(u)−c(v)|≥1 for each edge uv∈E(G) and |c(u)−c(v)|≥λ for each edge uv∈E(H) . The λ -backbone chromatic number BBCλ(G,H) is the smallest integer k such that there exists a λ -backbone coloring c of G with backbone H satisfying maxc(V(G))=k . A λ -backbone coloring c of G with backbone H is optimal if and only if maxc(V(G))=BBCλ(G,H) . In the paper we study the problem of finding optimal λ -backbone colorings of complete graphs with bipartite backbones. We present a linear algorithm that is 2 -approximate in general and 1.5 -approximate if backbone is connected. Next we show a quadratic algorithm for backbones being trees that finds optimal λ -backbone colorings provided λ is large enough.
Citations
-
1
CrossRef
-
0
Web of Science
-
1
Scopus
Authors (2)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
GRAPHS AND COMBINATORICS
no. 31,
edition 5,
pages 1487 - 1496,
ISSN: 0911-0119 - Language:
- English
- Publication year:
- 2015
- Bibliographic description:
- Janczewski R., Turowski K.: The Backbone Coloring Problem for Bipartite Backbones// GRAPHS AND COMBINATORICS. -Vol. 31, iss. 5 (2015), s.1487-1496
- DOI:
- Digital Object Identifier (open in new tab) 10.1007/s00373-014-1462-9
- Verified by:
- Gdańsk University of Technology
seen 140 times
Recommended for you
Minimum order of graphs with given coloring parameters
- G. Bacsó,
- P. Borowiecki,
- M. Hujter
- + 1 authors