dr inż. Krzysztof Turowski
Contact
 krzysztof.turowski@pg.edu.pl
Publication showcase

The computational complexity of the backbone coloring problem for planar graphs with connected backbones
In the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λbackbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NPcomplete or polynomially...

The computational complexity of the backbone coloring problem for boundeddegree graphs with connected backbones
Given a graph G, a spanning subgraph H of G and an integer λ>=2, a λbackbone coloring of G with backbone H is a vertex coloring of G using colors 1, 2, ..., in which the color difference between vertices adjacent in H is greater than or equal to lambda. The backbone coloring problem is to find such a coloring with maximum color that does not exceed a given limit k. In this paper, we study the backbone coloring problem for boundeddegree...

The Backbone Coloring Problem for Bipartite Backbones
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...
seen 324 times