Geodesic
Strong $k$-colorings of graphs
Diskretnaya Matematika, Tome 13 (2001) no. 1, pp. 78-89.

Voir la notice de l'article provenant de la source Math-Net.Ru

We say that a $k$-colouring $C_1,\ldots,C_k$ of a graph $G$ is strong if for any vertex $u\in VG$ there exists an index $i\in\{1,\ldots,k\}$ such that $u$ is adjacent to any vertex of the class $C_i$. We consider the class $S(k)$ of strongly $k$-colourable graphs and demonstrate that the problem to recognise $S(k)$ is NP-complete for any $k\ge 4$, whereas it is polynomially solvable for $k=3$. We characterise the class $S(3)$ in terms of forbidden induced subgraphs and solve the problem of uniqueness of a strong 3-colouring. 
@article{DM_2001_13_1_a4,
     author = {I. \'E. Zverovich},
     title = {Strong $k$-colorings of graphs},
     journal = {Diskretnaya Matematika},
     pages = {78--89},
     publisher = {mathdoc},
     volume = {13},
     number = {1},
     year = {2001},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2001_13_1_a4/}
}
TY  - JOUR
AU  - I. É. Zverovich
TI  - Strong $k$-colorings of graphs
JO  - Diskretnaya Matematika
PY  - 2001
SP  - 78
EP  - 89
VL  - 13
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2001_13_1_a4/
LA  - ru
ID  - DM_2001_13_1_a4
ER  - 
%0 Journal Article
%A I. É. Zverovich
%T Strong $k$-colorings of graphs
%J Diskretnaya Matematika
%D 2001
%P 78-89
%V 13
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2001_13_1_a4/
%G ru
%F DM_2001_13_1_a4
I. É. Zverovich. Strong $k$-colorings of graphs. Diskretnaya Matematika, Tome 13 (2001) no. 1, pp. 78-89. http://geodesic.mathdoc.fr/item/DM_2001_13_1_a4/

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, Moskva, 1982 | MR

[2] Brandstadt A., “Partitions of graphs into one or two independent sets and cliques”, Discrete Math., 152 (1998), 47–54 | DOI | MR

[3] Jensen T. R., Toft B., Graph coloring problems, Wiley, New York, 1995 | MR