A characterization of uniquely vertex colorable graphs using minimal defining sets (Q1297453): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q286082 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Miroslaw Truszczynski / rank | |||
Normal rank |
Revision as of 13:11, 12 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A characterization of uniquely vertex colorable graphs using minimal defining sets |
scientific article |
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