Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00418
VertexColoring with Defects
Patrizio Angelini,
Michael A. Bekos,
Felice De Luca,
Walter Didimo,
Michael Kaufmann,
Stephen Kobourov,
Fabrizio Montecchiani,
Chrysanthi N. Raftopoulou,
Vincenzo Roselli, and
Antonios Symvonis
Vol. 21, no. 3, pp. 313340, 2017. Regular paper.
Abstract Defective coloring is a variant of the traditional vertexcoloring 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 NPcomplete even for graphs with maximum vertexdegree $6$, hence answering an open question posed by Cowen et al. [Cowen, Goddard, Jesurum, J. Graph Theory, 1997], and for planar graphs with maximum vertexdegree $7$, and we prove that the (star, $3$)coloring problem is NPcomplete even for planar graphs with bounded maximum vertexdegree. On the other hand, we give lineartime 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.

Submitted: May 2016.
Reviewed: November 2016.
Revised: December 2016.
Accepted: December 2016.
Final: January 2017.
Published: February 2017.
