Nordhaus-Gaddum theorem for the distinguishing chromatic number (Q396886): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:10, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Nordhaus-Gaddum theorem for the distinguishing chromatic number |
scientific article |
Statements
Nordhaus-Gaddum theorem for the distinguishing chromatic number (English)
0 references
14 August 2014
0 references
Summary: \textit{E. A. Nordhaus} and \textit{J. W. Gaddum} [Am. Math. Mon. 63, 175--177 (1956; Zbl 0070.18503)] proved for any graph \(G\), that \(\chi(G) + \chi(\overline{G}) \leq n + 1\), where \(\chi\) is the chromatic number and \(n=|V(G)|\). \textit{H.-J. Finck} [in: Theory of Graphs, Proc. Colloq. Tihany, Hungary 1966, 99--113 (1968; Zbl 0157.55201)] characterized the class of graphs, which we call NG-graphs, that satisfy equality in this bound. In this paper, we provide a new characterization of NG-graphs, based on vertex degrees, which yields a new polynomial-time recognition algorithm and efficient computation of the chromatic number of NG-graphs. Our motivation comes from our theorem that generalizes the Nordhaus-Gaddum theorem to the distinguishing chromatic number. For any graph \(G, \chi_D(G) +\chi_D(\overline{G})\leq n+D(G)\). We call the set of graphs that satisfy equality in this bound NGD-graphs, and characterize the set of graphs that are simultaneously NG-graphs and NGD-graphs.
0 references
distinguishing number
0 references
distinguishing chromatic number
0 references
Nordhaus-Gaddum theorem
0 references