# Krzysztof Turowski - Profil naukowy - MOST Wiedzy

## Wyszukiwarka ## dr inż. Krzysztof Turowski

Brak danych

### Wybrane publikacje

• #### The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones

Given a graph G, a spanning subgraph H of G and an integer λ&gt;=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 bounded-degree...

Pełny tekst w serwisie zewnętrznym

• #### 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 NP-complete or polynomially...

Pełny tekst w serwisie zewnętrznym

• #### 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...

Pełny tekst w serwisie zewnętrznym

wyświetlono 296 razy