TY - JOUR
T1 - Vertex-coloring with defects
AU - Angelini, P.
AU - Bekos, M. A.
AU - De Luca, F.
AU - Didimo, W.
AU - Kaufmann, M.
AU - Kobourov, S.
AU - Montecchiani, F.
AU - Raftopoulou, C. N.
AU - Roselli, V.
AU - Symvonis, A.
N1 - Funding Information:
This work started at the Graph and Network Visualization (GNV) session of IISA ’15. Research supported in part by the MIUR project AMANDA, prot. 2012C4E3KT_001, by NSERC Canada, and by DFG grant Ka812/17-1. We thanks the anonymous reviewers of this paper for their valuable suggestions.
Publisher Copyright:
© 2017, Brown University. All rights reserved.
PY - 2017
Y1 - 2017
N2 - 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 k colors in which the monochromatic components are acyclic and have small diameter, namely we consider (edge, k)-colorings, in which the monochromatic components have diameter 1, and (star, k)-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. [9], 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.
AB - 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 k colors in which the monochromatic components are acyclic and have small diameter, namely we consider (edge, k)-colorings, in which the monochromatic components have diameter 1, and (star, k)-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. [9], 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.
UR - http://www.scopus.com/inward/record.url?scp=85021727000&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85021727000&partnerID=8YFLogxK
U2 - 10.7155/jgaa.00418
DO - 10.7155/jgaa.00418
M3 - Article
AN - SCOPUS:85021727000
VL - 21
SP - 313
EP - 340
JO - Journal of Graph Algorithms and Applications
JF - Journal of Graph Algorithms and Applications
SN - 1526-1719
IS - 3
ER -