Keszegh, Balázs and Zhu, X. (2020) A note about online nonrepetitive coloring k-trees. DISCRETE APPLIED MATHEMATICS, 285. pp. 108-112. ISSN 0166-218X
|
Text
1909.02612.pdf Download (126kB) | Preview |
Official URL: https://doi.org/10.1016/j.dam.2020.04.026
Abstract
We prove that it is always possible to color online nonrepetitively any (partial) k-tree (that is, graphs with tree-width at most k) with 4k colors. This implies that it is always possible to color online nonrepetitively cycles, trees and series-parallel graphs with 16 colors. Our results generalize the respective (offline) nonrepetitive coloring results. © 2020 The Author(s)
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | COLOR; Forestry; Offline; Trees (mathematics); Tree-width; Nonrepetitive coloring; Nonrepetitive coloring; Series-parallel graph; k-trees; Online coloring; Bounded tree-width; Color online; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 07 Feb 2023 15:08 |
| Last Modified: | 07 Feb 2023 15:08 |
| URI: | http://real.mtak.hu/id/eprint/158346 |
Actions (login required)
 |
Edit Item |
