Optimal Backbone Coloring of Split Graphs with Matching Backbones

Krzysztof Turowski

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 1, page 157-169
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Krzysztof Turowski. "Optimal Backbone Coloring of Split Graphs with Matching Backbones." Discussiones Mathematicae Graph Theory 35.1 (2015): 157-169. <http://eudml.org/doc/271216>.

@article{KrzysztofTurowski2015,
abstract = {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.},
author = {Krzysztof Turowski},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {backbone coloring; split graphs; matching},
language = {eng},
number = {1},
pages = {157-169},
title = {Optimal Backbone Coloring of Split Graphs with Matching Backbones},
url = {http://eudml.org/doc/271216},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Krzysztof Turowski
TI - Optimal Backbone Coloring of Split Graphs with Matching Backbones
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 1
SP - 157
EP - 169
AB - 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.
LA - eng
KW - backbone coloring; split graphs; matching
UR - http://eudml.org/doc/271216
ER -

References

top
  1. [1] P. Hammer and S. Földes, Split graphs, Congr. Numer. XIX (1977) 311-315. 
  2. [2] J. Miškuf, R. Skrekovski and M. Tancer, Backbone colorings of graphs with bounded degree, Discrete Appl. Math. 158 (2010) 534-542. doi:10.1016/j.dam.2009.11.015[Crossref][WoS] Zbl1215.05071
  3. [3] H. Broersma, F.V. Fomin, P.A. Golovach and G.J. Woeginger, Backbone colorings for graphs: tree and path backbones, J. Graph Theory 55 (2007) 137-152. doi:10.1002/jgt.20228[Crossref][WoS] Zbl1118.05031
  4. [4] H. Broersma, A general framework for coloring problems: old results, new results, and open problems, in: Combinatorial Geometry and Graph Theory: Indonesia- Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, J. Akiyama, E.T. Baskoro, M. Kano (Ed(s)), (Springer, 2003) 65-79. 
  5. [5] R. Janczewski, On an interrelation between travelling salesman problem and T- coloring of graphs, Proceedings of the Sixth International Conference: Advanced Computer Systems, ACS 1999, Szczecin, Poland (1999) 23-25. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.