Defective coloring is a variant of traditional vertex-coloring, according to which adjacent vertices are allowed to have the same color, as long as the monochromatic components induced by the corresponding edges 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, and acyclicity of the monochromatic components. In this paper we focus on defective colorings in which the monochromatic components are acyclic and have small diameter, namely, they form stars. For outerplanar graphs, we give a linear-time algorithm to decide if such a defective coloring exists with two colors and, in the positive case, to construct one. Also, we prove that an outerpath (i.e., an outerplanar graph whose weak-dual is a path) always admits such a two coloring. Finally, we present NP-completeness results for non-planar and planar graphs of bounded degree for the cases of two and three colors.
Angelini, P., Bekos, M.A., Kaufmann, M., Roselli, V. (2016). Vertex-coloring with star-defects. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.40-51). Springer Verlag [10.1007/978-3-319-30139-6_4].
Vertex-coloring with star-defects
ANGELINI, PATRIZIO;ROSELLI, VINCENZO
2016-01-01
Abstract
Defective coloring is a variant of traditional vertex-coloring, according to which adjacent vertices are allowed to have the same color, as long as the monochromatic components induced by the corresponding edges 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, and acyclicity of the monochromatic components. In this paper we focus on defective colorings in which the monochromatic components are acyclic and have small diameter, namely, they form stars. For outerplanar graphs, we give a linear-time algorithm to decide if such a defective coloring exists with two colors and, in the positive case, to construct one. Also, we prove that an outerpath (i.e., an outerplanar graph whose weak-dual is a path) always admits such a two coloring. Finally, we present NP-completeness results for non-planar and planar graphs of bounded degree for the cases of two and three colors.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
