Nordhaus-Gaddum theorem for the distinguishing chromatic number (Q396886): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Ann N. Trenk / rank | |||
Property / author | |||
Property / author: Ann N. Trenk / rank | |||
Normal rank | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C25 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68R10 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6330318 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
distinguishing number | |||
Property / zbMATH Keywords: distinguishing number / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
distinguishing chromatic number | |||
Property / zbMATH Keywords: distinguishing chromatic number / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Nordhaus-Gaddum theorem | |||
Property / zbMATH Keywords: Nordhaus-Gaddum theorem / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1203.5765 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distinguishing geometric graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Symmetry breaking in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Base size, metric dimension and other invariants of groups and graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graphs with large distinguishing chromatic number / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distinguishing Chromatic Number of Cartesian Products of Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bounds on the distinguishing chromatic number / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The distinguishing chromatic number / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distinguishing partitions and asymmetric uniform hypergraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5540282 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3328583 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The distinguishing number of Cartesian products of complete graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On primitive permutation groups with nontrivial global stabilizers. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distinguishing number of countable homogeneous relational structures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Breaking the Symmetries of the Book Graph and the Generalized Petersen Graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Complementary Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complementary graphs and the chromatic number / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distinguishing maps / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distinguishing numbers for graphs and groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distinguishability of locally finite trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distinguishing labeling of group actions / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 22:16, 8 July 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
0 references
0 references