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.
Autorzy
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1007/s00373-014-1462-9
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie wyróżnionym w JCR
- Język
- angielski
- Rok wydania
- 2015
Źródło danych: MOSTWiedzy.pl - publikacja "The Backbone Coloring Problem for Bipartite Backbones" link otwiera się w nowej karcie