Distinguishing chromatic number of random Cayley graphs

DOI10.1016/J.DISC.2017.06.002MaRDI QIDQ2012532zbMATH OpenOpenAlexFDO

Authors Niranjan Balachandran, Sajith Padinhatteeri

Publication date 1 August 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

distinguishing chromatic numberrandom Cayley graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: The extit{Distinguishing Chromatic Number} of a graph $G$, denoted $ch{i}_D(G)$, was first defined in cite{collins} as the minimum number of colors needed to properly color $G$ such that no non-trivial automorphism $phi$ of the graph $G$ fixes each color class of $G$. In this paper, we consider random Cayley graphs $Gamma(A,S)$ defined over certain abelian groups $A$ and show that with probability at least $1-n^{-Omega(logn)}$ we have, $ch{i}_D(Gamma)lechi(Gamma)+1$.

Recommendations

• The chromatic number of random Cayley graphs
• On the chromatic number of random Cayley graphs
• The chromatic number of random graphs
• The chromatic number of random graphs
• On the Chromatic Number of Random Graphs
• On the chromatic number of random graphs
• On the chromatic number of random graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Generalized chromatic numbers of random graphs

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Bounds on the distinguishing chromatic number
• On the automorphism groups of almost all Cayley graphs
• On the chromatic number of random Cayley graphs
• Symmetry breaking in graphs
• The Minimal Base Size of Primitive Solvable Permutation Groups
• The chromatic number of random Cayley graphs
• The distinguishing chromatic number
• χ_D(G), |Aut(G)|, and a variant of the motion lemma

Cited in

(4)

• The chromatic number of random Cayley graphs
• The distinguishing number and distinguishing chromatic number for posets
• Chromatic numbers of Cayley graphs on \(\mathbb Z\) and recurrence
• On the chromatic number of random Cayley graphs

This page was built for publication: Distinguishing chromatic number of random Cayley graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012532)