Algorytmiczne oszacowania liczby chromatycznej grafu

• Autorzy: Borowiecki P.

Warianty tytułu

EN

Algorithmic bounds on the chromatic number of a graph

• 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 jest problemem NP-trudnym, stąd duże zainteresowanie parametrami graf owym i, które można wykorzystać do opisu oszacowań wartości liczby chromatycznej. W pracy tej omawiamy własności parametrów wywodzących się z pojęcia funkcji potencjału grafu oraz badamy ich powiązania z klasycznymi parametrami takimi jak liczba Welsha-Powella oraz liczba Szekeresa-Wilfa. Przedstawiamy także wyniki eksperymentalnego porównania dwóch znanych algorytmów sekwencyjnych z algorytmami porządkującymi wierzchołki według wartości funkcji potencjału.

EN

The chromatic number of a graph is the smallest number of colors required to color its vertices such that no two adjacent vertices share a color. In the general case determining the chromatic number of a graph is NP-hard, thus any graph invariants useful in bounding it are of great interest. Within this paper we discuss the properties of the invariants originating in the notion of a potential function. We study their interdependencies and the relationships to the classical Welsh-Powell and Szekeres- Wilf numbers. We also present the results of experimental comparison of two known sequential algorithms to the algorithms that use orderings of vertices with respect to their potentials.

Słowa kluczowe

PL

liczba chromatyczna grafu; funkcja potencjału grafu; liczba Welsha-Powella; liczba Szekersa-Wilfa; algorytmy sekwencyjne; algorytmy porządkujące wierzchołki

EN

chromatic number of graph; NP-hard; graph potential function; Welsh-Powell numbers; Szekeres-Wilf numbers; sequential algorithms; algorithm ordering vertices

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2008
• Tom: T. 15
• Strony: 159--164
• Opis fizyczny: Bibliogr. 7 poz., tab.

Twórcy

autor

Borowiecki P.

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

Bibliografia

• [1] Acharya B. D., Vartak M. N.: On the construction oj graphs with given constant valence-difference(s) on each of their lines, Wiss. Zeitschrifte TH Ilmenau, 23 (6) (1977) 33-60.
• [2] Borowiecki P.: Nowe oszacowania górne dla liczby chromatycznej grafu i ich zastosowania algorytmiczne, Zesz. Nauk. Wydziału ETI Politechniki Gdańskiej, Ser. Technologie Informacyjne, 13 (2007) 435-442.
• [3] Kosowski A., Manuszewski K.: Classical coloring of graphs. W: Graph Colorings, Kubale M. (red.), Contemporary Mathematics 352, American Mathematical Society, Providence, 2004,1-19
• [4] Matula D.W.: A min-max theorem for graphs with application to graph coloring, SIAM Rev. 10 (1968) 481-482.
• [5] Matula D.W., Marble G., Isaacson J. D.: Graph coloring algorithms. W: Graph Theory and Computing, Read R. C. (red.), Academic Press, London, 1972, 109-122.
• [6] Szekeres G., Wilf S. H.: An inequality for the chromatic number of a graph, Joumal of Combinatorial Theory, 4 (1968) 1-3.
• [7] Welsh D. J. A., Powell M. B.: An upper bound for the chromatic number of a graph and its application to timetabling problem, Comp. J. 10 (1967) 85-86.