Geodesic
On perfect colorings of line graphs
Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 6, pp. 77-95.

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

The description of all feasible perfect colorings of line graphs, using two colors, is given, and all matrices of parameters of such colorings are listed. In addition, a simple construction that makes it possible to produce perfect colorings of arbitrary line graphs is proposed, and the perfect colorings which can be obtained with the use of the construction in question are characterized. Bibl. 13.
Keywords: perfect coloring, line graph.
Mots-clés : equitable partition 
@article{DA_2010_17_6_a5,
     author = {D. B. Khoroshilova},
     title = {On perfect colorings of line graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {77--95},
     publisher = {mathdoc},
     volume = {17},
     number = {6},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2010_17_6_a5/}
}
TY  - JOUR
AU  - D. B. Khoroshilova
TI  - On perfect colorings of line graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2010
SP  - 77
EP  - 95
VL  - 17
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2010_17_6_a5/
LA  - ru
ID  - DA_2010_17_6_a5
ER  - 
%0 Journal Article
%A D. B. Khoroshilova
%T On perfect colorings of line graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2010
%P 77-95
%V 17
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2010_17_6_a5/
%G ru
%F DA_2010_17_6_a5
D. B. Khoroshilova. On perfect colorings of line graphs. Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 6, pp. 77-95. http://geodesic.mathdoc.fr/item/DA_2010_17_6_a5/

[1] Avgustinovich S. V., Borodin O. V., Frid A. E., “Distributivnye raskraski ploskikh triangulyatsii minimalnoi stepeni 5”, Diskret. analiz i issled. operatsii. Ser. 1, 8:3 (2001), 3–16 | MR

[2] Vizing V. G., “Distributivnaya raskraska vershin grafa”, Diskret. analiz i issled. operatsii, 2:4 (1995), 3–12 | MR | Zbl

[3] Mogilnykh I. Yu., “O regulyarnosti sovershennykh raskrasok grafa Dzhonsona v dva tsveta”, Probl. peredachi informatsii, 43:4 (2007), 37–44 | MR | Zbl

[4] Puzynina S. A., “Periodichnost sovershennykh raskrasok beskonechnoi pryamougolnoi reshëtki”, Diskret. analiz i issled. operatsii. Ser. 1, 11:1 (2004), 79–92 | MR | Zbl

[5] Puzynina S. A., “Sovershennye raskraski vershin grafa $G(\mathbb Z^2)$ v tri tsveta”, Diskret. analiz i issled. operatsii. Ser. 2, 12:1 (2005), 37–54 | MR

[6] Fon-Der-Flaass D. G., “Sovershennye 2-raskraski giperkuba”, Sib. mat. zhurn., 48:4 (2007), 923–930 | MR | Zbl

[7] Kharari F., Teoriya grafov, KomKniga, M., 2006, 296 pp.

[8] Avgustinovich S. V., Mogilnykh I. Yu., “Perfect 2-colorings of Johnson graphs $J(6,3)$ and $J(7,3)$”, Second International Castle Meeting on Coding Theory and Applications, ICMCTA 2008, Proc . (Castillo de la Mota, Medina del Campo, Spain, September 15–19, 2008), Lect. Notes Comp. Sci., 5228, Springer-Verl., Berlin, 2008, 11–19 | MR | Zbl

[9] Axenovich M. A., “On multiple coverings of the infinite rectangular grid with balls of constant radius”, Discrete Math., 268:1–3 (2003), 31–49 | DOI | MR

[10] Cardosoa D. M., Rama P., “Spectral results on graphs with regularity constraint”, Linear Algebra Appl., 423:1 (2007), 90–98 | DOI | MR

[11] Godsil C., “Equitable partitions”, Combinatorics, Paul Erdős is Eighty, v. 1, Keszthely (Hungary), 1993, 173–192 | MR | Zbl

[12] Krotov D. S., Perfect colorings of $\mathbb Z^2$: nine colors, 2008, 177 pp., arXiv: 0901.0004[math.CO]

[13] Martin W. J., “Completely regular designs”, J. Combin. Designs, 6:4 (1998), 261–273 | 3.0.CO;2-D class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl