Modele i metody kolorowania grafów. Część I

• Autorzy: Kubale M.

Warianty tytułu

EN

Models and methods of graph coloring. Part I

• Języki publikacji: PL

Abstrakty

PL

Niniejszy artykuł jest pierwszą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano: (1) co można kolorować w grafie (np. wierzchołki, krawędzie, końcówki, ściany, jednocześnie wierzchołki i krawędzie) oraz (2) jak można kolorować (np. dzielenie kolorów, zawijanie kolorów). Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podajemy oszacowania na liczbę chromatyczną (indeks chromatyczny) oraz podajemy potencjalne zastosowania rozważanych modeli w problemach naukowo-technicznych.

EN

This is the first of a couple of review papers on models and methods of graph coloring. We present herein the main models of graph coloring from a practical point of view. In particular, we show: (1) what elements of a graph can be colored (e.g. vertices, edges, faces, incidences) and (2) how these elements can be colored (e.g. fractional coloring, circular coloring). Since graph coloring is NP-hard in various modifications and variants, we give simple bounds on the chromatic number (chromatic index) as well as we give potential applications of the chromatic methods in science and technology.

Słowa kluczowe

PL

kolorowanie grafu; liczba chromatyczna; indeks chromatyczny; NP-trudność

EN

graph coloring; chromatic number; chromatic index; NP-hardness

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2010
• Tom: R. 86, nr 9
• Strony: 115--117
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Kubale M.

• Politechnika Gdańska, Wydział Elektroniki, Telekomunikacji i Informatyki, Katedra Algorytmów iI Modelowania Systemów, ul. Narutowicza 11/12, 80-233 Gdańsk,

Bibliografia

• [1] Zuckerman D.: Linear degree extractors and the inapproximability of Max Clique and Chromatic Number. Proc. STOC’06, Seattle, 2006, p. 681-690.
• [2] Vizing V.G.: On an estimate of the chromatic class of a p-graph (po rosyjsku). Diskret. Analiz, vol.. 3, 1964, p. 25-30.
• [3] Kubale M. i in.: Optymalizacja dyskretna. Modele i metody kolorowania grafów. WNT, Warszawa, 2002.
• [4] Jensen T.R., Toft B.: Graph Coloring Problems. New York, Wiley, 1995.
• [5] Appel K., Haken W.: Every planar graph is four colorable. Pt. I: Discharging. Illinois J. Math., vol. 21, 1977, p. 429-490.
• [6] Garey M.R., Johnson D.S., Stockmeyer L.: Some simplified NP-complete graph problems. Theor. Comp. Sci., vol. 1, 1976, p. 237-267.
• [7] Kubale M.: Problem kolorowania wierzchołków grafów. Przegląd algorytmów i zastosowań. ZNPŚl., Ser. Automatyka, vol. 114, 1994, s. 187-198.
• [8] Brooks R.L.: On colouring the nodes of a network. Proc. Cambridge Philos. Soc., vol. 37, 1941, p. 194-197.
• [9] Halldórsson M.M.: A still better performance guarantee for approximate graph coloring, Inf. Process. Lett., vol. 45, 1993, p. 19-23.
• [10] Brẻlaz D.: New methods to color the vertices of a graph. Comm. ACM, vol. 22,1979, p. 251-256.
• [11] Tait P.G.: On the coloring of maps. Proc. Royal Soc. Edinburgh, Sec. A, vol. 10, 1880, p. 501-503.
• [12] Erdös P., Wilson R.J.: On the chromatic index of almost all graphs, J. Combinat. Theory, Ser. B, vol. 23, 1977, p. 255-257.
• [13] Kubale M.: Problem kolorowania krawędzi grafów. Przegląd algorytmów i zastosowań. ZNPŚl., Ser. Automatyka, vol. 117, 1996, s. 203-212.
• [14] Vince A.: Star chromatic number. J. Graph Theory, vol. 12, 1989, p. 551-559.
• [15] Stahl S.: n-tuple colorings and associated graphs. J. Combinat. Theory, Ser. B, vol. 20, 1976, 185-203.
• [16] Mycielski J.: On the coloring of graphs. Coll. Math., vol. 3, 1955, p. 161-162.