The smallest hard-to-color graphs for the classical, total and strong colorings of vertices

• Autorzy: Kubale M. , Manuszewski K.
• Języki publikacji: EN

Abstrakty

EN

: Let A(G) be the number of colors used by algorithm to color the vertices of graph G. A graph G is said to be hard-to-color (HC) (resp. slightly HC) if for every (resp. some) implementation of the algorithm A we have A(G) > chi(G), where chi(G) is the chromatic number of G. The study of HC graphs makes it possible design improved algorithms trying to avoid hard instances as far possible. Hard-to-color graphs are also good benchmarks for the evaluation of existing and future algorithms and provide an alternative way of assessing their quality. In this paper we demonstrate the smallest HC graphs for the best known coloring heuristics in classical applications, as well as when adapted to the chromatic sum coloring and strong coloring of vertices.

Słowa kluczowe

EN

benchmark; chromatic number; chromatic sum; graph oring; hard-to-color graph; NP-completeness; strong coloring

PL

optymalizacja; teoria grafów; złożoność obliczeniowa

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 1999
• Tom: Vol. 28, no 2
• Strony: 355--365
• Opis fizyczny: Bibliogr. 15 poz.,

Twórcy

autor

Kubale M.

autor

Manuszewski K.

• Technical University of Gdańsk, Foundations of Informatics Dept., Narutowicza 11/12, 80-952 Gdańsk,