.png){kind=icon}
.png){kind=icon}
Return
Tree coloring with predictions
.png){kind=icon}
OA
AI
DOI：10.1016/j.dam.2025.10.024.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Graph coloring is a notoriously challenging problem, especially when considering the online setting where each arriving vertex must be colored immediately and irreversibly. Even on trees, which are trivially two-colorable, achieving anything better than a logarithmic competitive ratio becomes impossible if the order of arrival is adversarially determined. We investigate tree coloring in a slightly relaxed model where vertices arrive online but in random order, focusing specifically on algorithms with predictions of varying reliability. Furthermore, we extend our analysis to all two-colorable graphs and provide matching lower bounds for both cases. (c) 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Keywords:
Online graph coloring
Competitive ratio
Random order
Predictions
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
D
IF:
1.1
Papers:
336
Citations:
7.7K
Organization
View more organizations