Edge colorings of graphs and multigraphs
C. J. McClain · OhioLink ETD Center (Ohio Library and Information Network) · 2008
Let G be a multigraph with maximum vertex degree ∆(G) and chromatic index χ E (G).A cluster in G is a subgraph that is maximally dense with respect to matchings in G.The cluster index ω E (G) is a measure of this density and is a lower bound for, then G has a unique minimal cluster.We show how to find this cluster by construction, and indicate how this construction might be used to prove Goldberg's conjecture that, for all multigraphs,Next, we consider another problem related to edge colorings.The chromatic index is most often defined to be the minimum size of a partition of the edge set of G into matchings.An equivalent definition is the minimum size of a cover of the edge set of G by matchings.We consider the analogous problem of covering the edge set of a simple graph G by subgraphs that are vertex-disjoint unions of cliques.We denote by χ K E (G) the minimum size of such a covering set, and investigate the specialfor n = 5, 6, 7, . . ., 12 by constructing a particular cover of L(K n ) using a greedy algorithm.We use this algorithm to show that χ K E (L(G)) ≤ 4 ln |G|/ ln 12 .Finally, we show that, in the case of G = K 13 , the minimum size of this particular cover is 5.