Wyszukiwarka
Abstrakt
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.
Cytowania
-
1
CrossRef
-
0
Web of Science
-
1
Scopus
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
GRAPHS AND COMBINATORICS
nr 31,
wydanie 5,
strony 1487 - 1496,
ISSN: 0911-0119 - Język:
- angielski
- Rok wydania:
- 2015
- Opis bibliograficzny:
- Janczewski R., Turowski K.: The Backbone Coloring Problem for Bipartite Backbones// GRAPHS AND COMBINATORICS. -Vol. 31, iss. 5 (2015), s.1487-1496
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00373-014-1462-9
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 147 razy
Publikacje, które mogą cię zainteresować
Minimum order of graphs with given coloring parameters
- G. Bacsó,
- P. Borowiecki,
- M. Hujter
- + 1 autorów