A characterization of uniquely vertex colorable graphs using minimal defining sets (Q1297453): Difference between revisions

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.