Graduate STEM Fellow Profile
Breeann Tonnsen Flesch
Thesis: On Interval Representations and Symmetries of Graphs
College/University: University of Colorado Denver
Research Advisor: Richard Lungren
Degree Sought: Ph.D. Applied Mathematics
Department: Department of Mathematical & Statistical Sciences
Research Focus: Characterizing which classes of graphs have various interval representations and coloring them to break any symmetries.
Description of Research
Interval p-graphs were introduced by Brown, Flink, and Lundgren in 2002 as a generalization of interval bigraphs. Little work has been done towards characterizing them. For interval bigraphs the only known forbidden subgraph characterization is for trees. As it appears to be quite difficult to find a forbidden subgraph characterization, we limit our work to an extension of trees called k-trees. We characterize p-interval k-trees as spiny interior k-lobsters and use this result to give a forbidden subgraph characterization. We apply a similar technique to 2-tree probe interval graphs, studied by Przulj and Corneil in 2005, and characterize them in terms of a subset of spiny interior $2$-lobsters. We are currently investigating which k-trees (k > 2) have probe interval presentations and unit interval p-representations.
A labeling of the vertices of a graph G is said to be distinguishing provided that no nontrivial automorphism of G preserves all of the vertex labels. The distinguishing number of G is the minimum number of labels in a distinguishing labeling of G. The distinguishing number, first introduced by Albertson and Collins in 1996, has been widely studied and a number of interesting results exist throughout the literature. We extend this notion 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(v) is in L(v) for all v. The list-distinguishing number of G is the minimum integer k such that G is L-distinguishable for any assignment L of lists with |L(v)|=k for all v. We have found the list-distinguishing number for many graph classes and are investigating more.
Example of how my research is integrated into my GK-12 experience
One example integrating my research is solving a scheduling problem by coloring an interval graph. I had the students represent a scheduling problem with a graph, which helped them understand the importance of representing a problem accurately and concisely. I then had them develop an algorithm for coloring the graph with the fewest colors possible. This helped enforce the algorithmic processes necessary in Algebra. They then solved the scheduling problem by coloring the graph. They were excited to see a ‘new’ type of math, and we then had many discussions about the nature and importance of math.