A characterization of uniquely vertex colorable graphs using minimal defining sets (Q1297453)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A characterization of uniquely vertex colorable graphs using minimal defining sets |
scientific article; zbMATH DE number 1321808
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A characterization of uniquely vertex colorable graphs using minimal defining sets |
scientific article; zbMATH DE number 1321808 |
Statements
A characterization of uniquely vertex colorable graphs using minimal defining sets (English)
0 references
5 June 2000
0 references
A graph is uniquely colorable if it admits exactly one \(\chi(G)\)-coloring (up to renaming of colors). A set \(S\) of colored vertices of a graph is called a defining set if it has a unique completion to a proper coloring into \(\chi(G)\) colors. The paper presents a result stating that if vertices of \(G\) are colored and all minimal defining sets with respect to this coloring have size \(\chi(G)-1\) then \(G\) is uniquely colorable.
0 references
characterization
0 references
uniquely colorable graphs
0 references
coloring
0 references
