Edge colorings of graphs and multigraphs

by McClain, Christopher

Abstract (Summary)
Let G be a multigraph. A cluster in G is a subgraph that is maximally dense with respect to matchings in G. The cluster index is a measure of this density and is a lower bound for the chromatic index. We prove that if G has at least one critical edge and if the cluster index is greater than the maximum degree plus one, 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, the chromatic index is at most the larger of the cluster index and the vertex degree plus one. 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 define the clique chromatic index to be the minimum size of such a covering set, and investigate the clique chromatic index of L(G), where L(G) is the line graph of G. We show that the clique chromatic index of the line graph of a clique on n vertices is 4 for n=5,6,7,...,12 by constructing a particular cover using a greedy algorithm. We use this algorithm to derive a logarithmic upper bound for the clique chromatic index of line graphs. Finally, we show that when G is a clique on 13 vertices, the minimum size of this particular cover is 5.
Bibliographical Information:


School:The Ohio State University

School Location:USA - Ohio

Source Type:Master's Thesis

Keywords:edge coloring multigraph goldberg chromatic index cluster clique line graph


Date of Publication:01/01/2008

© 2009 All Rights Reserved.