Distinguishing chromatic number of random Cayley graphs

DOI10.1016/J.DISC.2017.06.002zbMATH Open1367.05063arXiv1406.5358OpenAlexW2963702422MaRDI QIDQ2012532FDOQ2012532

Authors: Niranjan Balachandran, Sajith Padinhatteeri 

Publication date: 1 August 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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$.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Symmetry breaking in graphs
• The Minimal Base Size of Primitive Solvable Permutation Groups
• The chromatic number of random Cayley graphs
• On the automorphism groups of almost all Cayley graphs
• Bounds on the distinguishing chromatic number
• The distinguishing chromatic number
• χ_D(G), |Aut(G)|, and a variant of the motion lemma
• On the chromatic number of random Cayley graphs

Cited In (4)

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

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)