Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
A vertex coloring of a graph is called dynamic if the neighborhood of any vertex of degree at least 2 contains at least two vertices of distinct colors. Similarly to the chromatic number X(G) of a graph G, one can define its dynamic number Xd(G) (the minimum number of colors in a dynamic coloring) and dynamic chromatic number X2(G) (the minimum number of colors in a proper dynamic coloring). We prove that X2(G) ≤ X(G).Xd(G) and construct an infinite series of graphs for which this bound on X2(G) is tight. For a graph G, set k=(G)We prove that X2(G) ≤ (k+1)c. Moreover, in the case where k ≥ 3 and Δ(G) ≥ 3, we prove the stronger bound X2(G) ≤ kc.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 21-24 |
Число страниц | 4 |
Журнал | Journal of Mathematical Sciences (United States) |
Том | 232 |
Номер выпуска | 1 |
DOI | |
Состояние | Опубликовано - 1 июл 2018 |
ID: 36925057