A note on the asymptotic and computational complexity of graph distinguishability

zbMath0901.05052MaRDI QIDQ1385847

Alexander Russell, Ravi Sundaram

Publication date: 29 April 1998

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

Full work available at URL: https://eudml.org/doc/119614

zbMATH Keywords

computational complexityvertex coloring\(d\)-distinguishabilitycycle normvertex permutation

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Bounds for distinguishing invariants of infinite graphs, Generation of Colourings and Distinguishing Colourings of Graphs, Effective storage capacity of labeled graphs, Cartesian powers of graphs can be distinguished by two labels, Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's conjecture confirmed, Destroying automorphisms by fixing nodes, Distinguishing number of hierarchical products of graphs, Breaking graph symmetries by edge colourings, Local finiteness, distinguishing numbers, and Tucker's conjecture, Distinguishing threshold of graphs, Endomorphism breaking in graphs, Asymmetric colouring of locally compact permutation groups, The list distinguishing number of Kneser graphs, On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two, On the automorphism groups of rank-4 primitive coherent configurations, The distinguishing number of Cartesian products of complete graphs, A characterization of Johnson and Hamming graphs and proof of Babai's conjecture, Distinguishing Cartesian products of countable graphs, Edge motion and the distinguishing index, Infinite motion and 2-distinguishability of graphs and groups, Distinguishing index of maps, Distinguishing graphs of maximum valence 3, Distinguishing labellings of group action on vector spaces and graphs, On the spectral gap and the automorphism group of distance-regular graphs, On asymmetric colourings of claw-free graphs, Distinguishing labeling of group actions, On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results, The distinguishing number and distinguishing chromatic number for posets, The distinguishing index of infinite graphs, Coarse distinguishability of graphs with symmetric growth