Abstrakt
A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G. In this paper the problem of determinig the equitable coloring number for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas of cubic graphs is solvable in polynomial time, the problem of equitable coloring becomes NP-hard for these graphs. We provide polynomially solvable cases of coronas of cubic graphs and prove the NP-hardness in a general case. As a by-product we obtain a simple linear time algorithm for equitable coloring of such graphs which uses at most one extra color. Our algorithm is best possible, unless P=NP. Consequently, cubical coronas seem to be the only known class of graphs for which equitable coloring is harder than ordinary coloring.
Autorzy (2)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
ARS Mathematica Contemporanea
nr 10,
strony 333 - 347,
ISSN: 1855-3966 - Język:
- angielski
- Rok wydania:
- 2016
- Opis bibliograficzny:
- Furmańczyk H., Kubale M.: Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring// ARS Mathematica Contemporanea. -Vol. 10, nr. 2 (2016), s.333-347
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 101 razy
Publikacje, które mogą cię zainteresować
Equitable coloring of corona products of graphs
- H. Furmańczyk,
- K. Kaliraj,
- M. Kubale
- + 1 autorów