Limits of near-coloring of sparse graphs

Mickaël Montassier 1, 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Let a, b, d be non-negative integers. A graph G is (d, a, b)∗ -colorable if its vertex set can be partitioned into a + b sets I1,...,Ia,O1,...,Ob such that the graph G[Ii] induced by Ii has maximum degree at most d for 1 ≤ i ≤ a, while the graph G[Oi] induced by Oi is an edgeless graph for 1 ≤ i ≤ b. In this paper, we give two real-valued functions f and g such that any graph with maximum average degree at most f(d, a, b) is (d, a, b)∗ -colorable, and there exist non- (d, a, b)∗ -colorable graphs with average degree at most g(d, a, b). Both these functions converge (by lower values) to 2a + b when d tends to infinity. Counterintuitively, this implies that allowing a color to be of type Ii even for a large degree d increases the maximum average degree that guarantees the existence of a valid coloring only by 1. Using a color of type Ii (even with a very large degree d) is somehow less powerful than using two colors of type Oi (two stable sets).
Type de document :
Communication dans un congrès
2012 International Conference on Graph Theory, Combinatorics and Applications, Oct 2012, Zhejiang, China. 2012, 〈http://discrete.zjnu.edu.cn/icgca2012/?action-channel-name-en〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00782851
Contributeur : Mickael Montassier <>
Soumis le : mercredi 30 janvier 2013 - 16:51:33
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00782851, version 1

Citation

Mickaël Montassier. Limits of near-coloring of sparse graphs. 2012 International Conference on Graph Theory, Combinatorics and Applications, Oct 2012, Zhejiang, China. 2012, 〈http://discrete.zjnu.edu.cn/icgca2012/?action-channel-name-en〉. 〈lirmm-00782851〉

Partager

Métriques

Consultations de la notice

107