Nordhaus-Gaddum theorem for the distinguishing chromatic number

zbMath1298.05112arXiv1203.5765MaRDI QIDQ396886

Karen L. Collins, Ann N. Trenk

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.5765

zbMATH Keywords

Nordhaus-Gaddum theoremdistinguishing numberdistinguishing chromatic number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Coloring of graphs and hypergraphs (05C15)

Related Items (10)

Operations on independence numbers of certain graph classes ⋮ Split graphs and Nordhaus-Gaddum graphs ⋮ Extremal decompositions for Nordhaus-Gaddum theorems ⋮ Split graphs and block representations ⋮ Improving upper bounds for the distinguishing index ⋮ Distinguishing graphs by edge-colourings ⋮ Nordhaus-Gaddum and other bounds for the chromatic edge-stability number ⋮ Distinguishing chromatic numbers of complements of Cartesian products of complete graphs ⋮ On asymmetric colourings of claw-free graphs ⋮ Nordhaus-Gaddum type inequalities for the distinguishing index

Cites Work

• Unnamed Item
• Unnamed Item
• Distinguishing maps
• On primitive permutation groups with nontrivial global stabilizers.
• The distinguishing chromatic number
• Distinguishability of locally finite trees
• Distinguishing labeling of group actions
• On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results
• Distinguishing numbers for graphs and groups
• Symmetry breaking in graphs
• Graphs with large distinguishing chromatic number
• Bounds on the distinguishing chromatic number
• Distinguishing number of countable homogeneous relational structures
• Complementary graphs and the chromatic number
• The distinguishing number of Cartesian products of complete graphs
• Distinguishing Chromatic Number of Cartesian Products of Graphs
• Distinguishing partitions and asymmetric uniform hypergraphs
• Base size, metric dimension and other invariants of groups and graphs
• On Complementary Graphs
• Distinguishing geometric graphs
• Breaking the Symmetries of the Book Graph and the Generalized Petersen Graph
• On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach

This page was built for publication: Nordhaus-Gaddum theorem for the distinguishing chromatic number