Warianty tytułu
Algorithmic bounds on the chromatic number of a graph
Języki publikacji
Abstrakty
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.
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
Rocznik
Tom
Strony
159-164
Opis fizyczny
Bibliogr. 7 poz., tab.
Twórcy
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BPG5-0031-0053