Kara Shavo, Ph.D.
Professor of MathematicsEducation
University of South Carolina, Columbia, SC
Ph.D., Discrete Mathematics,
Dissertation: Matching Extension in the Powers of Graphs
Michigan State University, East Lansing, MI
M.S., Mathematics
University of Toledo, Toledo, OH
B.Ed., Mathematics
Research or Areas of Specialty
I study graph theory, where a “graph” is just another word for “network.” Most recently, I’ve focused on coloring graphs – their basic structure and substructure. A coloring graph is a metagraph, or graph of graphs. In particular, each node (or vertex) of this metagraph is a proper coloring of some graph G, and two nodes are connected (by an “edge”) if the two colorings differ at only one node in G. So, a coloring graph is a graph of proper graph colorings.
This begs the question: What is a proper graph coloring? Loosely speaking, graph colorings represent solutions to problems involving an “anti-relationship” of some kind, such as two chemicals that can’t be stored near each other or two committees that can’t meet at the same time because they share a member. We choose colors for the nodes so that two nodes in anti-relationship never get the same color. Generating a single proper graph coloring using the smallest number of colors is, in general, a very complex problem. It’s been proven that no efficient algorithm will ever completely solve the graph coloring problem. If a proper graph coloring can be found, however, a coloring graph can provide a way to move from one solution to another, generating more solutions. If the coloring graph is connected (an important, essential question), then all proper graph colorings may be found within the coloring graph.
Students have been integral to much of my research in coloring graphs. I’ve worked with five different honors research students during my time at PC. The most recent work, On the girth of forbidden subgraphs of coloring graphs, was published in the peer-reviewed journal Discrete Mathematics in 2024. I’ve also advised and guided many students on their Senior Capstone projects. The titles of students’ presentations include: Coronavirus Transmission in the NBA, Ramsey Theory: Is Complete Chaos Possible? Preferences, Voting, and Paradoxes, The Hungarian Method, Combinatorial Game Theory, Food Webs: Their Theory and Applications, and Graph Theory and Natural Language.
Classes at PC
- First Year Exploration
- Math for the Liberal Arts
- Calculus I
- Calculus III
- Math for Elementary Teachers
- Transition to Advanced Math
- Abstract Algebra
- Discrete Math With Graph Theory
- Linear Algebra
- Senior Seminar for Teachers
- Senior Capstone in Mathematics
Organizations
- Pi Mu Epsilon Mathematics Honor Society
Publications
On the Girth of Forbidden Subgraphs of Coloring Graphs, Discrete Mathematics, Vol 347, Issue 7, July, 2024.
Classifying Coloring Graphs, Discrete Mathematics, Vol. 339, No. 8, pp. 2100-2112, August, 2016.
A Result on Extendibility in the Powers of Graphs, Journal of Graph Theory, Vol. 56, No. 1, pp. 1-22, Fall, 2007. (Cited in Graph Factors and Matching Extensions, Qinglin Roger Yu and Guizhen Liu, Higher Eductation Press, 2009.)
Matching Extension in the Powers of n-connected Graphs. Journal of Graph Theory, Vol. 23, No. 4, 1996. (Cited in Graph Factors and Matching Extensions, Qinglin Roger Yu and Guizhen Liu, Higher Eductation Press, 2009.)