Repozytorium publikacji - Politechnika Gdańska

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

• dr hab. inż. Robert Janczewski link otwiera się w nowej karcie ,
• dr inż. Krzysztof Turowski link otwiera się w nowej karcie