Nowe oszacowania górne dla liczby chromatycznej grafu i ich zastosowania algorytmiczne

• Autorzy: Borowiecki P.

Warianty tytułu

EN

New upper bounds for the chromatic number of a graph and their algorithmic applications

• Języki publikacji: PL

Abstrakty

PL

Liczba chromatyczna grafu jest najmniejszą liczbą kolorów niezbędnych do pokolorowania jego wierzchołków w taki sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. W ogólnym przypadku problem wyznaczenia liczby chromatycznej grafu jest problemem NP-trudnym. W pracy tej wprowadzamy pojęcie funkcji potencjału określonej na wierzchołkach grafu i stosujemy ją w celu uzyskania nowych górnych oszacowań liczby chromatycznej. Porównujemy uzyskane oszacowania z ich klasycznymi odpowiednikami zależnymi od stopni wierzchołków. Wartości funkcji potencjału wykorzystujemy również do zdefiniowania nowych uporządkowań zbioru wierzchołków, co prowadzi do zdefiniowania dwóch nowych sekwencyjnych algorytmów kolorowania.

EN

Chromatic number of a graph is defined as the smallest number of colors required to color its vertices such that there does not exist a pair of adjacent vertices of the same color. In general it is NP-hard to determine the chromatic number of a graph. Within this paper we introduce the notion of a potential function of a graph defined on its vertex set and use it to establish new upper bounds on the chromatic number. The bounds are compared with their classical counterparts that use vertex degrees instead of potentials. Moreover, the values of a potential function are used to define new vertex orderings, what leads to new sequential graph coloring algorithms.

Słowa kluczowe

PL

liczba chromatyczna grafu; oszacowanie górne; funkcja potencjału; kolorowanie wierzchołków grafu

EN

chromatic number of graphs; upper bounds; potential function; sequential graph coloring algorithms

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2007
• Tom: T. 13
• Strony: 434--442
• Opis fizyczny: Bibliogr. 5 poz., rys., tab.

Twórcy

autor

Borowiecki P.

• Wydział Matematyki, Informatyki i Ekonometrii, Uniwersytet Zielonogórski

Bibliografia

• [1] Brooks R L: On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941) 194-197.
• [2] Matula D.W.: A min-max theorem for graphs with application to graph coloring, SIAM Rev. 10 (1968) 481-482.
• [3] Matula D.W., Marble G., Isaacson J. D.: Graph coloring algorithms. W: Read R. C. (red.) Graph Theory and Computing, Academic Press, London, 1972, 109-122.
• [4] Szekeres G., Wilf S. H.: An inequality for the chromatic number of a graph, Journal of Combinatorial Theory, 4 (1968) 1-3.
• [5] Welsh D. J. A., Powell M. B.: An upper bound for the chromatic number of a graph and its application to timetabling problem, Comput. J. 10 (1967) 85-86.