A note on the asymptotic and computational complexity of graph distinguishability
type: Item
instance of: scholarly article
title: A note on the asymptotic and computational complexity of graph distinguishability
zbMATH Open document ID: 0901.05052
author: Alexander Russell
author: Ravi Sundaram
published in: The Electronic Journal of Combinatorics
publication date: 1998-04-29T00:00:00Z
full work available at URL: https://eudml.org/doc/119614
full work available at URL: v5i1r23.html
review text: A graph \(G\) is \(d\)-distinguishable if it has a vertex coloring with \(d\) colors such that \(G\) has no color preserving automorphisms. (Adjacent vertices may receive the same color. Indeed, the only purpose of the graph in this theory seems to be to specify a group of vertex permutations.) The cycle norm of \(G\), \(c(G)\), is \(| V| - k\), where \(k\) is the greatest number of disjoint cycles in a non-trivial element of \(\Aut(G)\), regarded as a vertex permutation. Clearly, the more disjoint cycles that a vertex permutation has, the more symmetric colorings it will have. The authors use this observation to conclude that \[ c(G)\ln(d) > \ln(| \Aut(G)|)\text{ implies that \(G\) is \(d\)-distinguishable}. \] The second half of the paper examines the computational complexity of determining the \(d\)-distinguishability of a graph \(G\). Whether or not it is NP-hard is an open problem. The authors present compelling evidence that it is not coNP-hard. For a basic reference on this subject see \textit{M. O. Alberson} and \textit{K. L. Collins} [Electron. J. Comb. 3, No. 1, Paper R18 (1996; Zbl 0851.05088)].
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1147940
zbMATH Keywords: vertex coloring
zbMATH Keywords: cycle norm
zbMATH Keywords: vertex permutation
zbMATH Keywords: computational complexity
zbMATH Keywords: \(d\)-distinguishability
reviewed by: Herman J. Servatius
MaRDI profile type: Publication
Recommended article: Distinguishing trees in linear time
Recommended article: The Cost of Distinguishing Graphs
Recommended article: On computing the distinguishing numbers of trees and forests
Recommended article: Using determining sets to distinguish Kneser graphs
Recommended article: Infinite graphs with finite 2-distinguishing cost
Recommended article: Paint cost and the frugal distinguishing number
Recommended article: Distinguishing orthogonality graphs
Recommended article: Distinguishing index of graphs with simple automorphism groups
Recommended article: Symmetry breaking in graphs
Recommended article: On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two
description: scientific article; zbMATH DE number 1147940