Iwona Cieslik ; Marcin Kozik ; Piotr Micek - On-line coloring of $I_s$-free graphs

dmtcs:3472 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05) - https://doi.org/10.46298/dmtcs.3472
On-line coloring of $I_s$-free graphsArticle

Authors: Iwona Cieslik 1; Marcin Kozik 1; Piotr Micek 1

  • 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.


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]

Consultation statistics

This page has been seen 196 times.
This article's PDF has been downloaded 282 times.