Chromatic Connectivity of Graphs
Elliot Laforge · ScholarWorks - WMU (Western Michigan University) · 2016
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 byand c is a strong proper coloring if every two vertices u and v are connected by a proper u -v geodesic in G.The minimum number of colors required in a proper-path coloring (strong proper coloring) of G is called the proper connection number pc(G) (strong proper connection number spc(G)) of G.These concepts are inspired by the well-known and well-studied concepts of rainbow coloring, rainbow connection number rc(G), strong rainbow coloring and strong connection number src(G) of a connected graph G.We investigate the relationship among these four edge colorings as well as proper edge colorings in graphs, the best known edge colorings.Several realization results are established for the five edge coloring parameters pc(G), spc(G), rc(G), src(G) and chromatic index χ (G) of a connected graph G (the minimum number of colors required in a proper edge coloring of G).Furthermore, the exact values of pc(G) and spc(G) are determined for several well-known classes of graphsWe study proper-path colorings in those graphs obtained from some well-known graph operations, namely joins of graphs and Cartesian products of graphs, permutations graphs, line graphs, powers of graphs, coronas of graphs, vertex or edge deletions as well as the well-known class of unicyclic graphs.In fact, proper connection numbers are determined for all joins and Cartesian products of two nontrivial connected graphs, for all iterated line graphs and powers of a given connected graph.For a connected graph G, sharp lower and upper bounds are established for the proper connection number of (i) the k-iterated corona of G in terms of pc(G) and k and (ii) the vertex or edge deletion graphs G -v and G -e where v is a non-cut-vertex of G and e is a non-bridge of G in terms of pc(G) and the degree of v. Since it is in general very challenging to determine pc(G) and spc(G) for any given connected graph G, we establish several sharp bounds for pc(G) and spc (G) in terms of the order, size or maximum degree of the graph G.We extend the study of proper connection (also called chromatic connection) in connected graphs to the study of the chromatic connectivity of ℓ-connected graphs for some integer ℓ ≥ 2. Suppose that G is an ℓ-connected graph for some positive integer ℓ.It then follows from a well-known theorem of Whitney that for every integer k with 1 ≤ k ≤ ℓ and every two distinct vertices u and v of G, the graph G contains k internally disjoint u -v paths.An edge coloring of a connected graph G is called a proper k-path coloring of G for some positive integer k if for every two distinct vertices u and v of G, there exist at least k internally disjoint proper u -v paths.The minimum number of the colors required in a proper k-paththe proper connection number of G.We investigate the proper k-connectivity of highly connected graphs.In particular, we establish sharp lower bounds for the proper k-connectivity of certain complete bipartite graphs K r,s of order r + s where 2 ≤ r ≤ s, which are improvements of some known results.Furthermore, the proper 2-connectivity of K r,s has been determined for all integers r and s with 2 ≤ r ≤ s.The exact values of pc k (K r,s ) have been determined for some specific values of k and for several other classes of complete bipartite graphs.Open questions are also presented on this parameter of complete bipartite graphs.A connected graph G of diameter at least 2 is ℓ-geodesic connected for some positive integer ℓ if for every two nonadjacent vertices u and v of G, there exist at least ℓ internally disjoint u -v geodesics in G. Thus, every two nonadjacent vertices u and v are connected by ℓ internally disjoint u -v paths of length d(u, v).An edge coloring of a graph G is called a proper k-geodesic coloring (or a strong proper k-path coloring) of G for some positive integer k if for every two nonadjacent vertices u and v of G, there exist at least k internallyis the strong proper connection number of a connected graph G.We investigate the strong proper k-connectivity of complete bipartite graphs, establish lower bounds for the strong proper k-connectivity of certain complete bipartite graphs and determine exact values of spc k (K r,s ) for some specific values of k and for some class of complete bipartite graphs.Conjectures and open questions are also presented in this area of research.Furthermore, we introduce several related topics for further study.