Characterizations of Graphs Having Large Proper Connection Numbers

Chira Lumduanhom, Elliot Laforge, and Ping Zhang. "Characterizations of Graphs Having Large Proper Connection Numbers." Discussiones Mathematicae Graph Theory 36.2 (2016): 439-453. <http://eudml.org/doc/277127>.

@article{ChiraLumduanhom2016,
abstract = {Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. If P is a proper u − v path of length d(u, v), then P is a proper u − v geodesic. An edge coloring c is a proper-path coloring of a connected graph G if every pair u, v of distinct vertices of G are connected by a proper u − v path in G, and c is a strong proper-path coloring if every two vertices u and v are connected by a proper u− v geodesic in G. The minimum number of colors required for a proper-path coloring or strong proper-path coloring of G is called the proper connection number pc(G) or strong proper connection number spc(G) of G, respectively. If G is a nontrivial connected graph of size m, then pc(G) ≤ spc(G) ≤ m and pc(G) = m or spc(G) = m if and only if G is the star of size m. In this paper, we determine all connected graphs G of size m for which pc(G) or spc(G) is m − 1,m − 2 or m − 3.},
author = {Chira Lumduanhom, Elliot Laforge, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge coloring; proper-path coloring; strong proper-path coloring},
language = {eng},
number = {2},
pages = {439-453},
title = {Characterizations of Graphs Having Large Proper Connection Numbers},
url = {http://eudml.org/doc/277127},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Chira Lumduanhom
AU - Elliot Laforge
AU - Ping Zhang
TI - Characterizations of Graphs Having Large Proper Connection Numbers
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 2
SP - 439
EP - 453
AB - Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. If P is a proper u − v path of length d(u, v), then P is a proper u − v geodesic. An edge coloring c is a proper-path coloring of a connected graph G if every pair u, v of distinct vertices of G are connected by a proper u − v path in G, and c is a strong proper-path coloring if every two vertices u and v are connected by a proper u− v geodesic in G. The minimum number of colors required for a proper-path coloring or strong proper-path coloring of G is called the proper connection number pc(G) or strong proper connection number spc(G) of G, respectively. If G is a nontrivial connected graph of size m, then pc(G) ≤ spc(G) ≤ m and pc(G) = m or spc(G) = m if and only if G is the star of size m. In this paper, we determine all connected graphs G of size m for which pc(G) or spc(G) is m − 1,m − 2 or m − 3.
LA - eng
KW - edge coloring; proper-path coloring; strong proper-path coloring
UR - http://eudml.org/doc/277127
ER -