Geodesic
Near-colorings: non-colorable graphs and NP-completeness
M. Montassier1 ; P. Ochem2
1LIRMM, Université de Montpellier
2LIRMM, CNRS
The electronic journal of combinatorics, Tome 22 (2015) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A graph $G$ is $(d_1,...,d_l)$-colorable if the vertex set of $G$ can be partitioned into subsets $V_1,\ldots ,V_l$ such that the graph $G[V_i]$ induced by the vertices of $V_i$ has maximum degree at most $d_i$ for all $1 \leq i \leq 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) \neq (0,0)$ and $g\geq3$, 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 determine 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.
DOI : 10.37236/3509
Classification : 05C15, 05C10, 05C07, 05C35
Mots-clés : planar graphs, improper coloring, complexity

M. Montassier  1   ; P. Ochem  2

1 LIRMM, Université de Montpellier
2 LIRMM, CNRS 
@article{10_37236_3509,
     author = {M. Montassier and P. Ochem},
     title = {Near-colorings: non-colorable graphs and {NP-completeness}},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {1},
     doi = {10.37236/3509},
     zbl = {1308.05052},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3509/}
}
TY  - JOUR
AU  - M. Montassier
AU  - P. Ochem
TI  - Near-colorings: non-colorable graphs and NP-completeness
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3509/
DO  - 10.37236/3509
ID  - 10_37236_3509
ER  - 
%0 Journal Article
%A M. Montassier
%A P. Ochem
%T Near-colorings: non-colorable graphs and NP-completeness
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3509/
%R 10.37236/3509
%F 10_37236_3509
M. Montassier; P. Ochem. Near-colorings: non-colorable graphs and NP-completeness. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/3509

Cité par Sources :