On-line coloring of $I_s$-free graphs

Iwona Cieslik 1 Marcin Kozik 1 Piotr Micek 1
1 Algorithmics Research Group
UJ - Jagiellonian University [Krakow]
Abstract : 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.
Type de document :
Communication dans un congrès
David, René and Gardy, Danièle and Lescanne, Pierre and Zaionc, Marek. Computational Logic and Applications, CLA '05, 2005, Chambéry, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05), pp.61-68, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01183336
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 11 août 2015 - 08:54:46
Dernière modification le : mercredi 10 mai 2017 - 17:40:18
Document(s) archivé(s) le : jeudi 12 novembre 2015 - 10:12:38

Fichier

dmAF0104.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01183336, version 1

Collections

Citation

Iwona Cieslik, Marcin Kozik, Piotr Micek. On-line coloring of $I_s$-free graphs. David, René and Gardy, Danièle and Lescanne, Pierre and Zaionc, Marek. Computational Logic and Applications, CLA '05, 2005, Chambéry, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05), pp.61-68, 2005, DMTCS Proceedings. 〈hal-01183336〉

Partager

Métriques

Consultations de la notice

61

Téléchargements de fichiers

109