Splitting a planar graph of girth 5 into two forests with trees of small diameter Научная публикация
| Журнал |
Discrete Mathematics
ISSN: 0012-365X , E-ISSN: 1872-681X |
||
|---|---|---|---|
| Вых. Данные | Год: 2018, Том: 341, Номер: 7, Страницы: 2058-2067 Страниц : 10 DOI: 10.1016/j.disc.2018.04.007 | ||
| Ключевые слова | Forest; List colouring; Pk-free colouring; Path partition; Planar graph | ||
| Авторы |
|
||
| Организации |
|
Реферат:
In 1985, Mihok and recently Axenovich, Ueckerdt, and Weiner asked about the minimum integer g∗>3 such that every planar graph with girth at least g∗ admits a 2-colouring of its vertices where the length of every monochromatic path is bounded from above by a constant. By results of Glebov and Zambalaeva and of Axenovich et al., it follows that 5≤g∗≤6. In this paper we establish that g∗=5. Moreover, we prove that every planar graph of girth at least 5 admits a 2-colouring of its vertices such that every monochromatic component is a tree of diameter at most 6. We also present the list version of our result. © 2018 Elsevier B.V.
Библиографическая ссылка:
Glebov A.N.
Splitting a planar graph of girth 5 into two forests with trees of small diameter
Discrete Mathematics. 2018. V.341. N7. P.2058-2067. DOI: 10.1016/j.disc.2018.04.007 WOS Scopus OpenAlex
Splitting a planar graph of girth 5 into two forests with trees of small diameter
Discrete Mathematics. 2018. V.341. N7. P.2058-2067. DOI: 10.1016/j.disc.2018.04.007 WOS Scopus OpenAlex
Даты:
| Поступила в редакцию: | 22 нояб. 2016 г. |
| Принята к публикации: | 10 апр. 2018 г. |
Идентификаторы БД:
| Web of science: | WOS:000434743300022 |
| Scopus: | 2-s2.0-85046342684 |
| OpenAlex: | W2800944282 |