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

• Autorzy: Kubale M.

Warianty tytułu

EN

Models and methods of graph coloring – part II.

• Języki publikacji: PL

Abstrakty

PL

Niniejszy artykuł jest drugą 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 różne kryteria i ograniczenia modyfikujące kolorowanie klasyczne. Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podano oszacowania na liczbę chromatyczną (indeks chromatyczny) oraz podano potencjalne zastosowania rozważanych modeli w problemach naukowo-technicznych.

EN

This is the second 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 various criteria and modifications of classical coloring model. 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ść; algorytm wielomianowy; NP-hardness

EN

graph coloring; chromatic number; chromatic index; polynomial algorithm

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2012
• Tom: R. 88, nr 11a
• Strony: 51--55
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Kubale M.

• Politechnika Gdańska, Katedra Algorytmów i Modelowania Systemów,

Bibliografia

• [1] Zuckerman D., Linear degree extractors and the inapproximability of Max Clique and Chromatic Number. Proc. STOC’06 Conf., Seattle (2006), 681-690
• [2] Vizing V.G., On an estimate of the chromatic class of a p-graph (po rosyjsku). Diskret. Analiz, 3 (1964), 25-30
• [3] Kubale M., Modele i metody kolorowania grafów. Część I, Przegląd Elektrotechniczny, 86 (2010), 115-117
• [4] Kubale M. i in., Optymalizacja dyskretna. Modele i metody kolorowania grafów. WNT, Warszawa (2002)
• [5] Jensen T.R., Tof t B., Graph Coloring Problems, New York, Wiley (1995)
• [6] Chartrand G. Zhang P., Chromatic Graph Theory. Chapman and Hall, Boca Raton (2009)
• [7] Meyer W., Equitable coloring, Amer. Math. Monthly, 80 (1973), 920-928
• [8] Kierstead H.A., Kostochka A.V., Mydlarz M., Szemeredi E., A fast algorithm for equitable coloring. Combinatorica, 30 (2010), 217-224
• [9] Kubicka E., Schwenk A.J., An introduction to chromatic sums, Proc. Annual ACM Comp. Sci. Conf. (1989), 39-45
• [10] Frank O., Harary F., Planthold M., The line-distinguishing chromatic number of a graph, Ars Combin., 14 (1982), 241-252
• [11] Asratian A., Kamalian R., Investigation on interval edgecolorings of graphs. J. Combin. Theory. Ser. B, 62 (1994), p. 34-43
• [12] Giaro K., Kubale M., Małafiejski M., Compact scheduling in open shop with zero-one time operations, INFOR, 37 (1999), 37-47
• [13] Bouchard M., Hertz A., Desaulniers G., Lower bounds and tabu search algorithm for minimum deficiency problem, J. Combin. Optimiz., 17 (2009), 168-191
• [14]Petrosyan P.A., Sargsyan H.E., On resistance of graphs, Disc. Appl. Math., 159 (2011), 1889-1900
• [15] Griggs J.R., Yeh R.K., Labelling graphs with a condition at distance 2, SIAM J. Disc. Math., 5 (1992), 586-595.
• [16] Schreiber R., A new implementation of sparse Gaussian elimination, ACM Trans. Math. Software, 8 (1982), 256-276