Wyszukiwarka
Abstrakt
A complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively), and the Grundy number Γ(G) defined as the largest k admitting a complete coloring &varphi with exactly k colors such that every vertex v∈V of color F(v) has a neighbor of color i for all 1 <= i < F(v). The inequality chain χ(G) <= Γ(G) <= ψ(G) obviously holds for all graphs G. A triple (f,g,h) of positive integers at least 2 is called realizable if there exists a connected graph G with χ(G) = f, Γ(G) = g, and ψ(G) = h. Chartrand et al. (A note on graphs with prescribed complete coloring numbers, J. Combin. Math. Combin. Comput. LXXIII (2010) 77-84) found the list of realizable triples. In this paper we determine the minimum number of vertices in a connected graph with chromatic number f, Grundy number g, and achromatic number h, for all realizable triples (f,g,h) of integers. Furthermore, for f = g = 3 we describe the (two) extremal graphs for each h >= 6. For h = 4 and h = 5, there are more extremal graphs, their description is contained as well.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Autorzy (4)
-
Gábor Bacsó
- Hungarian Academy of Sciences .
-
Mihály Hujter
- Budapest University of Technology and Economics .
-
Zsolt Tuza
- Hungarian Academy of Sciences .
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.disc.2014.12.002
- Licencja
- Copyright (2014 Elsevier B.V)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
DISCRETE MATHEMATICS
nr 338,
wydanie 4,
strony 621 - 632,
ISSN: 0012-365X - Język:
- angielski
- Rok wydania:
- 2015
- Opis bibliograficzny:
- Bacsó G., Borowiecki P., Hujter M., Tuza Z.: Minimum order of graphs with given coloring parameters// DISCRETE MATHEMATICS. -Vol. 338, iss. 4 (2015), s.621-632
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.disc.2014.12.002
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 156 razy