Journal of Combinatorics

Volume 3 (2012)

Number 4

Proper connection with many colors

Pages: 683 – 693

DOI: https://dx.doi.org/10.4310/JOC.2012.v3.n4.a6

Authors

Shinya Fujita (Department of Integrated Design Engineering, Maebashi Institute of Technology, Maebashi, Japan)

Aydin Gerek (Department of Mathematics, Lehigh University, Bethlehem, Penn., U.S.A.)

Colton Magnant (Department of Mathematical Sciences, Georgia Southern University, Statesboro, Ga., U.S.A.)

Abstract

We say an edge-colored graph is properly connected if, between every pair of vertices, there exists a properly colored path. For a graph $G$, define the proper connection number $pc(G)$ to be the minimum number of colors $k$ such that there exists a $k$-coloring of $E(G)$ which is properly connected. In this work, we study conditions on $G$ which force upper bounds on $pc(G)$.

Keywords

proper edge-coloring, connectivity, proper connection, alternating paths

Published 21 February 2013