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/

[1] M. Chellali, A. Khelladi and F. Maffray, Exact double domination in graphs, Discuss. Math. Graph Theory 25 (2005) 291-302. doi: 10.7151/dmgt.1282

[2] W. Goddard and R. Melville, Coloring subgraphs with restricted amounts of hues, Open Math. 15 (2017) 1117-1180. doi: 10.1515/math-2017-0098

[3] G. Hahn, J. Kratochvíl, J. Širáň and D. Sotteau, On the injective chromatic number of graphs, Discrete Math. 256 (2002) 179-192. doi: 10.1016/S0012-365X(01)00466-6

[4] F. Kramer and H. Kramer, A survey on the distance-colouring of graphs, Discrete Math. 308 (2008) 422-426. doi: 10.1016/j.disc.2006.11.059

[5] J.-M. Laborde, Sur le nombre domatique du n-cube et une conjecture de Zelinka, European J. Combin. 8 (1987) 175-177. doi: 10.1016/S0195-6698(87)80008-2

[6] P.M. Weichsel, Dominating sets in n-cubes, J. Graph Theory 18 (1994) 479-488. doi: 10.1002/jgt.3190180506

[7] B. Zelinka, Domatic numbers of cube graphs, Math. Slovaca 32 (1982) 117-119.