Geodesic
Almost Injective Colorings
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 225-239

Voir la notice de l'article provenant de la source Library of Science

We define an almost-injective coloring as a coloring of the vertices of a graph such that every closed neighborhood has exactly one duplicate. That is, every vertex has either exactly one neighbor with the same color as it, or exactly two neighbors of the same color. We present results with regards to the existence of such a coloring and also the maximum (minimum) number of colors for various graph classes such as complete k-partite graphs, trees, and Cartesian product graphs. In particular, we give a characterization of trees that have an almost-injective coloring. For such trees, we show that the minimum number of colors equals the maximum degree, and we also provide a polynomial-time algorithm for computing the maximum number of colors, even though these questions are NP-hard for general graphs.
Keywords: coloring, injective, closed neighborhood, domatic 
@article{DMGT_2019_39_1_a17,
     author = {Goddard, Wayne and Melville, Robert and Xu, Honghai},
     title = {Almost {Injective} {Colorings}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {225--239},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a17/}
}
TY  - JOUR
AU  - Goddard, Wayne
AU  - Melville, Robert
AU  - Xu, Honghai
TI  - Almost Injective Colorings
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 225
EP  - 239
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a17/
LA  - en
ID  - DMGT_2019_39_1_a17
ER  - 
%0 Journal Article
%A Goddard, Wayne
%A Melville, Robert
%A Xu, Honghai
%T Almost Injective Colorings
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 225-239
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a17/
%G en
%F DMGT_2019_39_1_a17
Goddard, Wayne; Melville, Robert; Xu, Honghai. Almost Injective Colorings. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 225-239. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a17/