Geodesic
Optimal adjacent vertex-distinguishing edge-colorings of circulant graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1341-1359 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A k-proper edge-coloring of a graph G is called adjacent vertex-distinguishing if any two adjacent vertices are distinguished by the set of colors appearing in the edges incident to each vertex. The smallest value k for which G admits such coloring is denoted by χ_a^' (G). We prove that χ_a^'(G)=2R+1 for most circulant graphs C_n( [[ 1,R ]] ).
Keywords: proper edge-coloring, circulant graph, distinguishing vertices, adjacent vertex-distinguishing, chromatic number 
@article{DMGT_2024_44_4_a6,
     author = {Gravier, Sylvain and Signargout, Hippolyte and Slimani, Souad},
     title = {Optimal adjacent vertex-distinguishing edge-colorings of circulant graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1341--1359},
     year = {2024},
     volume = {44},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a6/}
}
TY  - JOUR
AU  - Gravier, Sylvain
AU  - Signargout, Hippolyte
AU  - Slimani, Souad
TI  - Optimal adjacent vertex-distinguishing edge-colorings of circulant graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1341
EP  - 1359
VL  - 44
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a6/
LA  - en
ID  - DMGT_2024_44_4_a6
ER  - 
%0 Journal Article
%A Gravier, Sylvain
%A Signargout, Hippolyte
%A Slimani, Souad
%T Optimal adjacent vertex-distinguishing edge-colorings of circulant graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1341-1359
%V 44
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a6/
%G en
%F DMGT_2024_44_4_a6
Gravier, Sylvain; Signargout, Hippolyte; Slimani, Souad. Optimal adjacent vertex-distinguishing edge-colorings of circulant graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1341-1359. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a6/

[1] M. Aigner, E. Triesch and Zs. Tuza, Irregular assignments and vertex-distinguishing edge-colorings of graphs, Ann. Discrete Math. 52 (1992) 1–9. https://doi.org/10.1016/S0167-5060(08)70896-3

[2] S. Akbari, H. Bidkhori and N. Nosrati, r-strong edge colorings of graphs, Discrete Math. 306 (2006) 3005–3010. https://doi.org/10.1016/j.disc.2004.12.027

[3] P.N. Balister, E. Györi, J. Lehel and R.H. Schelp, Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math. 21(1) (2007) 237. https://doi.org/10.1137/S0895480102414107

[4] P.N. Balister, O.M. Riordan and R.H. Schelp, Vertex-distinguishing edge colorings of graphs, J. Graph Theory 42 (2003) 95–109. https://doi.org/10.1002/jgt.10076

[5] J.L. Baril, H. Kheddouci and O. Togni, Vertex distinguishing egde-and total-colorings of Cartesian and other product graphs, Ars Combin. 107 (2012) 109–127.

[6] J.L. Baril, H. Kheddouci and O. Togni, Adjacent vertex distinguishing edge-colorings of meshes and hypercubes, Australas. J. Combin. 35 (2006) 89–102.

[7] C. Bazgan, A. Harkat-Benhamdine, Hao Li and M. Woźniak, On the vertex-distinguishing proper edge-colorings of graphs, J. Combin. Theory Ser. B 75 (1999) 288–301. https://doi.org/10.1006/jctb.1998.1884

[8] A.C. Burris and R.H. Schelp, Vertex-distinguishing proper edge-colorings, J. Graph Theory 26 (1997) 73–82. https://doi.org/10.1002/(SICI)1097-0118(199710)26:23.0.CO;2-C

[9] G.J. Chang, M. Montassier, A. Pecher and A. Raspaud, Strong chromatic index of planar graphs with large girth, Discuss. Math. Graph Theory 34 (2014) 723–733. https://doi.org/10.7151/dmgt.1763

[10] O. Favaron, H. Li and R.H. Schelp, Strong edge colorings of graphs, Discrete Math. 159 (1996) 103–109. https://doi.org/10.1016/0012-365X(95)00102-3

[11] J.L. Fouquet and J.L. Jolivet, Strong edge-colorings of graphs and applications to multi-k-gons, Ars Combin. 16(A) (1983) 141–150.

[12] J.L. Fouquet and J.L. Jolivet, Strong edge-colorings of cubic planar graphs, Progress in Graph Theory, Academic Press, Toronto (1984) 247–264.

[13] H. Hatami, \delta + 300 is a bound on the adjacent vertex distinguishing edge chromatic number, J. Combin. Theory Ser. B 95 (2005) 246–256. https://doi.org/10.1016/j.jctb.2005.04.002

[14] H. Hocquard and M. Montassier, Adjacent vertex-distinguishing edge coloring of graphs with maximum degree \Delta, J. Comb. Optim. 26 (2013) 152–160. https://doi.org/10.1007/s10878-011-9444-9

[15] M. Mockovčiaková and R. Soták, Arbitrarily large difference between d-strong chromatic index and its trivial lower bound, Discrete Math. 313 (2013) 2000–2006. https://doi.org/10.1016/j.disc.2013.01.026

[16] T. Wang and X. Zhao, Odd graph and its applications to the strong edge coloring, Appl. Math. Comput. 325 (2018) 246–251. https://doi.org/https://doi.org/10.1016/j.amc.2017.11.057

[17] W. Wang and Y. Wang, Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree, J. Comb. Optim. 19 (2010) 471–485. https://doi.org/10.1007/s10878-008-9178-5

[18] Z. Zhang, L. Liu and J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623–626. https://doi.org/10.1016/S0893-9659(02)80015-5