Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: backbone coloring

Sortuj według:

Ogranicz wyniki do:

Optimal Backbone Coloring of Split Graphs with Matching Backbones

100%

Turowski K.

Discussiones Mathematicae Graph Theory

2015

tom 35

nr 1

157-169

For a graph G with a given subgraph H, the backbone coloring is defined as the mapping c : V (G) → N+ such that |c(u) − c(v)| ≥ 2 for each edge {u, v} ∈ E(H) and |c(u) − c(v)| ≥ 1 for each edge {u, v} ∈ E(G). The backbone chromatic number BBC(G,H) is the smallest integer k such that there exists a backbone coloring with maxv∈V (G) c(v) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number

100%

Broersma H., Marchal B., Paulusma D., Salman A.

Discussiones Mathematicae Graph Theory

2009

tom 29

nr 1

143-162

We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring for G and H is a proper vertex coloring V→ {1,2,...} of G in which the colors assigned to adjacent vertices in H differ by at least λ. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers. The main outcome of earlier studies is that the minimum number l of colors, for which such colorings V→ {1,2,...,l} exist, in the worst case is a factor times the chromatic number (for path, tree, matching and star backbones). We show here that for split graphs and matching or star backbones, l is at most a small additive constant (depending on λ) higher than the chromatic number. Our proofs combine algorithmic and combinatorial arguments. We also indicate other graph classes for which our results imply better upper bounds on l than the previously known bounds.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Broersma H.

1 Marchal B.

1 Paulusma D.

1 Salman A.

1 Turowski K.

1 2015

1 2009

Wyniki wyszukiwania

Optimal Backbone Coloring of Split Graphs with Matching Backbones

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number