Near-colorings: non-colorable graphs and NP-completeness - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles The Electronic Journal of Combinatorics Year : 2015

Near-colorings: non-colorable graphs and NP-completeness

Mickaël Montassier
Pascal Ochem


A graph G is (d1,...,dl)-colorable if the vertex set of G can be partitioned into subsets V1 , . . . , Vl such that the graph G[Vi ] induced by the vertices of Vi has maximum degree at most di for all 1 ≤ i ≤ l. In this paper, we focus on complexity aspects of such colorings when l = 2, 3. More precisely, we prove that, for any fixed integers k, j, g with (k, j) ̸= (0, 0) and g ≥ 3, either every planar graph with girth at least g is (k,j)-colorable or it is NP-complete to determine whether a planar graph with girth at least g is (k,j)-colorable. Also, for any fixed integer k, it is NP-complete to deter- mine whether a planar graph that is either (0,0,0)-colorable or non-(k,k,1)-colorable is (0, 0, 0)-colorable. Additionally, we exhibit non-(3, 1)-colorable planar graphs with girth 5 and non-(2, 0)-colorable planar graphs with girth 7.
Fichier principal
Vignette du fichier
3509-13132-2-PB.pdf (309.52 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-01263770 , version 1 (25-03-2017)



Mickaël Montassier, Pascal Ochem. Near-colorings: non-colorable graphs and NP-completeness. The Electronic Journal of Combinatorics, 2015, 22 (1), pp.#P1.57. ⟨10.37236/3509⟩. ⟨lirmm-01263770⟩
92 View
184 Download



Gmail Facebook X LinkedIn More