(k,1)-coloring of sparse graphs

Abstract : A graph G is ( k , 1 ) -colorable if the vertex set of G can be partitioned into subsets V 1 and V 2 such that the graph G [ V 1 ] induced by the vertices of V 1 has maximum degree at most k and the graph G [ V 2 ] induced by the vertices of V 2 has maximum degree at most 1 . We prove that every graph with maximum average degree less than 10 k + 22 3 k + 9 admits a ( k , 1 ) -coloring, where k ≥ 2 . In particular, every planar graph with girth at least 7 is ( 2 , 1 ) -colorable, while every planar graph with girth at least 6 is ( 5 , 1 ) -colorable. On the other hand, when k ≥ 2 we construct non- ( k , 1 ) -colorable graphs whose maximum average degree is arbitrarily close to 14 k 4 k + 1 .
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2012, 312 (6), pp.1128-1135. 〈10.1016/j.disc.2011.11.031〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00782819
Contributeur : Mickael Montassier <>
Soumis le : mercredi 30 janvier 2013 - 16:27:49
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Lien texte intégral

Identifiants

Citation

Oleg Borodin, Anna Ivanova, Mickaël Montassier, André Raspaud. (k,1)-coloring of sparse graphs. Discrete Mathematics, Elsevier, 2012, 312 (6), pp.1128-1135. 〈10.1016/j.disc.2011.11.031〉. 〈lirmm-00782819〉

Partager

Métriques

Consultations de la notice

174