Document Type
Lecture
Publication Date
3-28-2012
Abstract
A graph is said to be well-covered if all maximal independent vertex sets have the same cardinality. Well-covered trees can be characterized as trees with a perfect matching consisting of pendant edges, i.e. edges incident with a vertex of degree one. The main result of the talk is a generalization of this result to k-trees, with pendant cliques playing in k-trees the role which pendant edges play in trees. A graph is said to be uniquely colorable if, modulo permutations of the colors, there is only one coloring in the minimal number of colors. It is easy to see that k-trees are uniquely colorable. A (possibly) new class of uniquely colorable graphs, the k-frames, will be introduced, generalizing the class of k-trees.
Relational Format
presentation
Recommended Citation
Payne, Wanda, "Well-covered k-trees, k-frames, and unique colorability" (2012). Combinatorics Seminar. 64.
https://egrove.olemiss.edu/math_combinatorics/64
