The backbone coloring problem for small graphs

• Autorzy: Janczewski R. , Turowski K.
• Języki publikacji: EN

Abstrakty

EN

In this paper we investigate the values of the backbone chromatic number, derived from a mathematical model for the problem of minimization of bandwidth in radio networks, for small connected graphs and connected backbones (up to 7 vertices). We study the relationship of this parameter with the structure of the graph and compare the results with the solutions obtained using the classical graph coloring algorithms (LF, IS), modified for the backbone coloring problem.

Słowa kluczowe

EN

frequency assignment; graph coloring; backbone chromatic number

PL

przydział częstotliwości; kolorowanie grafów; szkieletowa liczba chromatyczna

• Wydawca: Wydawnictwo Politechniki Łódzkiej
• Czasopismo: Journal of Applied Computer Science
• Rocznik: 2014
• Tom: Vol. 22, nr 2
• Strony: 19--30
• Opis fizyczny: Bibliogr. 4 poz.

Twórcy

autor

Janczewski R.

• Gdansk University of Technology, Department of Algorithms and Systems Modelling, Narutowicza 11/12, 80-233 Gdańsk, Poland

autor

Turowski K.

• Gdansk University of Technology, Department of Algorithms and Systems Modelling, Narutowicza 11/12, 80-233 Gdańsk, Poland

Bibliografia

• [1] Broersma, H. J., A general framework for coloring problems: old results, new results, and open problems, In: Combinatorial Geometry and Graph Theory, Springer Berlin / Heidelberg, 2003, pp. 65–79.
• [2] Janczewski, R. and Turowski, K., The backbone coloring problem for bipartite backbones, submitted.
• [3] Broersma, H. J., Fujisawa, J., Marchal, B., Paulusma, D., Salman, A. N. M., and Yoshimoto, K., λ-backbone colorings along pairwise disjoint stars and matchings, Discrete Mathematics, Vol. 309, No. 18, 2009, pp. 5596–5609.
• [4] Miskuf, J., Skrekovski, R., and Tancer, M., Backbone colorings of graphs with bounded degree, Discrete Applied Mathematics, Vol. 158, No. 5, 2010, pp. 534–542.