Edge Coloring Graphs with Distance Restrictions
Nicholas Davidson · Occidental College Scholar (Occidental College) · 2002
Using probabilistic methods developed by Michael Molloy and Bruce Reed, we attempt to prove a conjecture that says the strong chromatic index for bipartite graphs is less than or equal to 5/4(D)^2$ where (D) is the maximum degree of a vertex in the bipartite graph. In the process we discovered some interesting characteristics of line graphs of bipartite graphs, namely that the clique graph of the line graph yields the original graph minus vertices of degree 1. This fact not only holds for bipartite graphs but for all triangle-free graphs.