A characterization of uniquely vertex colorable graphs using minimal defining sets (Q1297453): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Miroslaw Truszczynski / rank | |||
Property / reviewed by | |||
Property / reviewed by: Miroslaw Truszczynski / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Advances in graph theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Forcing Structures and Cliques in Uniquely Vertex Colorable Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Uniquely colorable graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Defining sets in vertex colorings of graphs and latin rectangles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4002255 / rank | |||
Normal rank |
Latest revision as of 21:33, 28 May 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