Well-covered Graphs, Unique Colorability, and Covering Range

<p>A graph is called well-covered if all of its maximal independent sets have the same cardinality. We give a characterization of well-covered k-trees. A graph is said to be uniquely χ-colorable if, modulo permutations of colors, it has exactly one proper χ-coloring. The k-trees with at least k+1 vertices are minimal uniquely (k +1)-colorable, i.e., they have the minimal number of edges necessary for uniquely (k+1)-colorable graphs. We introduce the k-frames, a new class of minimal uniquely (k+1)-colorable graphs that generalizes the k-trees. </p> <p>The covering range of a graph is the difference between the cardinality of a largest maximal independent set of a graph and the cardinality of a smallest maximal independent set of the graph. We give the covering range for some cubic graphs and a class of k-regular graphs. </p>

Name thesis:degree_name

Ph.D. in Mathematics

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Year dc:date.available

2013

Author dc:creator

• Payne, Wanda Renea

Contributors dc:contributor

• William Staton
• Talmadge James Reid
• Dawn Wilkins

• covering range
• unique colorability
• well-covered
• Mathematics

Repository record dc:identifier

https://egrove.olemiss.edu/etd/1439

OAI identifier oai:identifier

oai:egrove.olemiss.edu:etd-2438