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.
Authors
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1007/s00373-014-1462-9
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie wyróżnionym w JCR
- Language
- angielski
- Publication year
- 2015
