A sharp upper bound on k-color connectivity

Adam Jump


How many dierent types of security do we need to ensure that our network is fully protected? Likewise, how do we effectively optimize a trucking route? While we have vastly different questions, our answer is the same. We apply edge-colorings on graphs to answer this question. Represent each terminal hub with a vertex, and each direct link between hubs with an edge between the two vertices. We call this collection of vertices and edges a graph. For each type of connection security, assign a distinct color to the corresponding edges. If we want to transfer information from hub u to hub v through a series of consecutive direct links between intermediate hubs, then we draw a path in G. Our question now becomes, "Given a graph G, how many colors do we need for there to exist some edge-coloring where, between every two vertices u and v in G there exists a u,v-path using k different colors?" In other words, what is the k-color connection number of G, or cck(G)? We show the k-color connection number for wheel graphs and provide upper bounds for complete bipartite graphs as well as doubly-chorded cycles of small length. In doing so, we improve on the conjecture by Coll et al. that cck(G) <= 2k - 1 for all graphs G.


Graph Theory, Communication Networks, Edge Coloring

Full Text: PDF


  • There are currently no refbacks.