- Batch Coloring of Graphs.
- Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin.
Algorithmica. Accepted for Publication.
We study two versions of graph coloring, where the goal is to
assign a positive integer color to each vertex of an input graph
such that adjacent vertices do not receive the same color
assignment. For classic vertex coloring, the goal is to minimize
the maximum color used, and for the sum coloring problem, the goal
is to minimize the sum of colors assigned to all input vertices.
In the offline variant, the entire graph is presented at once, and
in online problems, one vertex is presented for coloring at each
time, and the only information is the identity of its neighbors
among previously known vertices. In batched graph coloring,
vertices are presented in k
batches, for a fixed integer
k ≥ 2
, such that the vertices of a batch are presented as a
set, and must be colored before the vertices of the next batch are
presented. This last model is an intermediate model, which bridges
between the two extreme scenarios of the online and offline
models. We provide several results, including a general result for
sum coloring and results for the classic graph coloring problem on
restricted graph classes: We show tight bounds for any graph class
containing trees as a subclass (forests, bipartite graphs, planar
graphs, and perfect graphs, for example), and an interesting
result for interval graphs and k=2
, where the value of the
(strict and asymptotic) competitive ratio depends on whether the
graph is presented with its interval representation or not.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.
open access (189 KB)
The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.
Other publications by the author.