Batch Coloring of Graphs

DOI10.1007/978-3-319-51741-4_5MaRDI QIDQ2971156zbMATH OpenOpenAlexFDO

Authors Leah Epstein, Kim S. Larsen, Asaf Levin, Joan Boyar, Lene M. Favrholdt

Publication date 4 April 2017

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.02997, https://portal.findresearcher.sdu.dk/da/publications/47a242a1-a9f5-414a-a834-3fe2a67aefa0

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Abstract: 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 in k batches, for a fixed integer k > 1, 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.

Recommendations

• Batch coloring of graphs
• Batch Coloring Flat Graphs and Thin
• Graph colorings
• scientific article; zbMATH DE number 3935075
• Graph colouring algorithms
• Dynamic coloring of graphs
• Dynamic graph coloring
• Dynamic graph coloring
• scientific article; zbMATH DE number 1863545
• Coloring permutation graphs in parallel

Cites work

• scientific article; zbMATH DE number 4170931 (Why is no real title available?)
• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• A note on first-fit coloring of interval graphs
• Batch Coloring of Graphs
• Batched bin packing
• Batched bin packing revisited
• First-fit coloring on interval graphs has performance ratio at least 5
• Improved lower bounds for semi-online bin packing problems
• Lower bound for 3-batched bin packing
• Lower bounds for on-line graph coloring
• More on batched bin packing
• On chromatic sums and distributed resource allocation
• On sum coloring and sum multi-coloring for restricted families of graphs
• On the sum coloring problem on interval graphs
• On-line and first fit colorings of graphs
• Online coloring known graphs
• The chromatic sum of a graph: history and recent developments
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(6)

• Batch Coloring Flat Graphs and Thin
• CsegGraph: a graph colouring instance generator
• Batch coloring of graphs
• Batch Coloring of Graphs
• Graph coloring with rejection
• Graph Coloring with Rejection

This page was built for publication: Batch Coloring of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2971156)