(k,1)-coloring of sparse graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Discrete Mathematics Year : 2012

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

Dates and versions

lirmm-00782819 , version 1 (30-01-2013)

Identifiers

Cite

Oleg V. Borodin, Anna O. Ivanova, Mickaël Montassier, André Raspaud. (k,1)-coloring of sparse graphs. Discrete Mathematics, 2012, 312 (6), pp.1128-1135. ⟨10.1016/j.disc.2011.11.031⟩. ⟨lirmm-00782819⟩
150 View
0 Download

Altmetric

Share

More