This thesis focuses on two main topics: interval representations and symmetries of graphs. A graph is interval if to every vertex υ ∈ V(G), we can assign an interval of the real line, Iυ such that xy ∈ E(G) if and only if Ix ∩ Iy ≠ ∅. We call the set of intervals of the real line the interval representation of the graph. Interval graphs were characterized by the absence of induced cycles larger than 3 and asteroidal triples by Lekkerkerker and Boland [38] in 1962. Subsequently variations on the interval theme have been introduced, including probe interval graphs and the interval p-graph, which is a generalization of the interval bigraph.
A natural extension of interval graphs, called interval bigraphs, were introduced by Harary, Kabell, and McMorris [30] in 1982. A bipartite graph G = (X, Y) is an interval bigraph if to every vertex, υ ∈ V(G), we can assign an interval of the real line, Iυ, such that xy ∈ E(G) if and only if Ix ∩ Iy ≠ ∅ and x ∈ X and y ∈ Y. Initially it was thought that the natural extension of asteroidal triples of vertices to asteroidal triples of edges along with induced cycles larger than 4 would be a forbidden subgraph characterization [30]. However that was not to be, and there is no forbidden subgraph characterization of interval bigraphs to date. The only forbidden subgraph characterization in the literature is for cycle-free interval bigraphs in [15].
The second concentration of this thesis, symmetries of graphs, began in 1996 with a paper by Albertson and Collins [2]. A coloring of the vertices of a graph G, f : V( G) → {1, ..., r} is said to be r-distinguishing if no nontrivial autornorphism of the graph preserves all of the vertex colors. The distinguishing number of a graph G is defined by D(G) = min { r | G has a coloring that is r-distinguishing}. Albertson and Collins determined the distinguishing number for graphs that realize the dihedral group. We let Dn denote the dihedral group of order 2n, which is the group of symmetries of a regular n-gon. Albertson and Collins [2] proved that if G realizes Dn then D(G) = 2 unless n = {3, 4, 5, 6, 10} in which case D(G) is either 2 or 3.
Since Albertson and Collins introduced this topic, there has been much investigation into distinguishing colorings. Areas of these investigations include the distinguishing number of Cartesian products ([1], [6], [35], [37]), determining a bound on the distinguishing number ([19], [36]), and the distinguishing number of trees and forests ([17]).
In our investigations we generalize distinguishing colorings to list-distinguishing colorings. Given a family L of lists assigning available colors to the vertices of G, we say that G is L-distinguishable if there is a distinguishing coloring f of G such that f(υ) ∈ L(υ) for all υ. The list-distinguishing number of G, written Dℓ( G), is the smallest positive integer k such that G is L-distinguishable for any assignment L of lists with |L(υ)| = k for all υ. Since all of the lists can be identical, we see that D(G) ≤ Dℓ( G).
Here we determine the list-distinguishing number for several families of graphs and highlight a number of distinctions between the problems of distinguishing and list-distinguishing a graph. We first give a Brooks-type result for list-distinguishing colorings. By determining precisely when the distinguishing number is 3 in small cases, we show that the list-distinguishing number is equal to the distinguishing number for all graphs that realize the dihedral group. Lastly, we give the list-distinguishing number for some Cartesian product graphs. (Abstract shortened by UMI.)
