Geodesic
Vertex-Coloring with Defects
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation (WALCOM 2016) , Tome 21 (2017) no. 3, pp. 313-340.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Defective coloring is a variant of the traditional vertex-coloring in which adjacent vertices are allowed to have the same color, as long as the induced monochromatic components have a certain structure. Due to its important applications, as for example in the bipartisation of graphs, this type of coloring has been extensively studied, mainly with respect to the size, degree, diameter, and acyclicity of the monochromatic components. We focus on defective colorings with $\kappa$ colors in which the monochromatic components are acyclic and have small diameter, namely we consider (edge, $\kappa$)-colorings, in which the monochromatic components have diameter $1$, and (star, $\kappa$)-colorings, in which they have diameter $2$. We prove that the (edge, $3$)-coloring problem remains NP-complete even for graphs with maximum vertex-degree $6$, hence answering an open question posed by Cowen et al. [Cowen, Goddard, Jesurum, J. Graph Theory, 1997], and for planar graphs with maximum vertex-degree $7$, and we prove that the (star, $3$)-coloring problem is NP-complete even for planar graphs with bounded maximum vertex-degree. On the other hand, we give linear-time algorithms for testing the existence of (edge, $2$)-colorings and of (star, $2$)-colorings of partial $2$-trees. Finally, we prove that outerpaths, a notable subclass of outerplanar graphs, always admit (star, $2$)-colorings.
DOI : 10.7155/jgaa.00418
Keywords: vertex coloring, defects, monochromatic components 
@article{JGAA_2017_21_3_a4,
     author = {Patrizio Angelini and Michael Bekos and Felice De Luca and Walter Didimo and Michael Kaufmann and Stephen Kobourov and Fabrizio Montecchiani and Chrysanthi Raftopoulou and Vincenzo Roselli and Antonios Symvonis},
     title = {Vertex-Coloring with {Defects}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {313--340},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2017},
     doi = {10.7155/jgaa.00418},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00418/}
}
TY  - JOUR
AU  - Patrizio Angelini
AU  - Michael Bekos
AU  - Felice De Luca
AU  - Walter Didimo
AU  - Michael Kaufmann
AU  - Stephen Kobourov
AU  - Fabrizio Montecchiani
AU  - Chrysanthi Raftopoulou
AU  - Vincenzo Roselli
AU  - Antonios Symvonis
TI  - Vertex-Coloring with Defects
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 313
EP  - 340
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00418/
DO  - 10.7155/jgaa.00418
LA  - en
ID  - JGAA_2017_21_3_a4
ER  - 
%0 Journal Article
%A Patrizio Angelini
%A Michael Bekos
%A Felice De Luca
%A Walter Didimo
%A Michael Kaufmann
%A Stephen Kobourov
%A Fabrizio Montecchiani
%A Chrysanthi Raftopoulou
%A Vincenzo Roselli
%A Antonios Symvonis
%T Vertex-Coloring with Defects
%J Journal of Graph Algorithms and Applications
%D 2017
%P 313-340
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00418/
%R 10.7155/jgaa.00418
%G en
%F JGAA_2017_21_3_a4
Patrizio Angelini; Michael Bekos; Felice De Luca; Walter Didimo; Michael Kaufmann; Stephen Kobourov; Fabrizio Montecchiani; Chrysanthi Raftopoulou; Vincenzo Roselli; Antonios Symvonis. Vertex-Coloring with Defects. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation  (WALCOM 2016)
					, Tome 21 (2017) no. 3, pp. 313-340. doi : 10.7155/jgaa.00418. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00418/

Cité par Sources :