Processing math: 46%

Iwona Cieslik ; Marcin Kozik ; Piotr Micek - On-line coloring of Is-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 Is-free graphsConference paper

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 Is-free graphs, i.e., graphs in which the maximal size of an independent set is at most s1. An old Szemerédi's result implies that for each on-line algorithm A there exists an on-line presentation of an Is-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 315 times.
This article's PDF has been downloaded 365 times.