# OhioLINKElectronic Theses & Dissertations Center

Search ETDs:
Edge colorings of graphs and multigraphs
McClain, Christopher

2008, Doctor of Philosophy, Ohio State University, Mathematics.

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.

G. Neil Robertson (Advisor)
Akos Seress (Committee Member)
Boris Pittel (Committee Member)
97 p.

# APA Citation

McClain, C. (2008). Edge colorings of graphs and multigraphs. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

# MLA Citation

McClain, Christopher. "Edge colorings of graphs and multigraphs." Electronic Thesis or Dissertation. Ohio State University, 2008. OhioLINK Electronic Theses and Dissertations Center. 20 Jan 2018.

# Chicago Citation

McClain, Christopher "Edge colorings of graphs and multigraphs." Electronic Thesis or Dissertation. Ohio State University, 2008. https://etd.ohiolink.edu/

# Files

osu1211904033.pdf (463.19 KB) View|Download