- Batch Coloring of Graphs.
- Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin.
In 14th Workshop on Approximation and Online Algorithms (WAOA), volume 10138 of Lecture Notes in Computer Science, pages 52-64. Springer, 2017.
In graph coloring problems, 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
graph 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
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
(e.g., forests, bipartite graphs, planar graphs, and perfect graphs),
and a surprising 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.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
open access (302 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.