Discrete Mathematics & Theoretical Computer Science |

- 1 Algorithmics Research Group

An on-line vertex coloring algorithm receives vertices of a graph in some externally determined order. Each new vertex is presented together with a set of the edges connecting it to the previously presented vertices. As a vertex is presented, the algorithm assigns it a color which cannot be changed afterwards. The on-line coloring problem was addressed for many different classes of graphs defined in terms of forbidden structures. We analyze the class of $I_s$-free graphs, i.e., graphs in which the maximal size of an independent set is at most $s-1$. An old Szemerédi's result implies that for each on-line algorithm A there exists an on-line presentation of an $I_s$-free graph $G$ forcing A to use at least $\frac{s}{2}χ ^{(G)}$ colors. We prove that any greedy algorithm uses at most $\frac{s}{2}χ^{(G)}$ colors for any on-line presentation of any $I_s$-free graph $G$. Since the class of co-planar graphs is a subclass of $I_5$-free graphs all greedy algorithms use at most $\frac{5}{2}χ (G)$ colors for co-planar $G$'s. We prove that, even in a smaller class, this is an almost tight bound.

Source: HAL:hal-01183336v1

Volume: DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05)

Section: Proceedings

Published on: January 1, 2005

Imported on: May 10, 2017

Keywords: planar graph,on-line algorithm,graph coloring,[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO],[INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]

This page has been seen 196 times.

This article's PDF has been downloaded 282 times.