Geodesic
The Proper Diameter of a Graph
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 107-125.

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

A proper edge-coloring of a graph is a coloring in which adjacent edges receive distinct colors. A path is properly colored if consecutive edges have distinct colors, and an edge-colored graph is properly connected if there exists a properly colored path between every pair of vertices. In such a graph, we introduce the notion of the graph’s proper diameter—which is a function of both the graph and the coloring—and define it to be the maximum length of a shortest properly colored path between any two vertices in the graph. We consider various families of graphs to find bounds on the gap between the diameter and possible proper diameters, paying singular attention to 2-colorings.
Keywords: diameter, properly connected, proper diameter 
@article{DMGT_2020_40_1_a7,
     author = {Coll, Vincent and Hook, Jonelle and Magnant, Colton and McCready, Karen and Ryan, Kathleen},
     title = {The {Proper} {Diameter} of a {Graph}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {107--125},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a7/}
}
TY  - JOUR
AU  - Coll, Vincent
AU  - Hook, Jonelle
AU  - Magnant, Colton
AU  - McCready, Karen
AU  - Ryan, Kathleen
TI  - The Proper Diameter of a Graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 107
EP  - 125
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a7/
LA  - en
ID  - DMGT_2020_40_1_a7
ER  - 
%0 Journal Article
%A Coll, Vincent
%A Hook, Jonelle
%A Magnant, Colton
%A McCready, Karen
%A Ryan, Kathleen
%T The Proper Diameter of a Graph
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 107-125
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a7/
%G en
%F DMGT_2020_40_1_a7
Coll, Vincent; Hook, Jonelle; Magnant, Colton; McCready, Karen; Ryan, Kathleen. The Proper Diameter of a Graph. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 107-125. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a7/

[1] E. Andrews, E. Laforge, C. Lumduanhom and P. Zhang, On proper-path colorings in graphs, J. Combin. Math. Combin. Comput. 97 (2016) 189–207.

[2] V. Borozan, S. Fujita, A. Gerek, C. Magnant, Y. Manoussakis, L. Montero and Zs. Tuza, Proper connection of graphs, Discrete Math. 312 (2012) 2550–2560. doi:10.1016/j.disc.2011.09.003

[3] G. Chartrand, G. L. Johns, A. K. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85–98.

[4] G. Chartrand, G. Johns, K. McKeon and P. Zhang, The rainbow connectivity of a graph, Networks 54 (2009) 75–81. doi:10.1002/net.20296

[5] S. Fujita, A. Gerek and C. Magnant, Proper connection with many colors, J. Comb. 3 (2012) 683–693. doi:10.4310/JOC.2012.v3.n4.a6

[6] E. Laforge, C. Lumduanhom and P. Zhang, Characterizations of graphs having large proper connection numbers, Discuss. Math. Graph Theory 36 (2016) 439–453. doi:10.7151/dmgt.1867

[7] E. Laforge, C. Lumduanhom and P. Zhang, Chromatic-connection in graphs, Congr. Numer. 225 (2015) 37–54.

[8] X. Li and C. Magnant, Properly colored notions of connectivity—a dynamic survey, Theory Appl. Graphs 0 (2015), Iss. 1, Article 2. doi:10.20429/tag.2015.000102