Record Details

DSpace at IIT Bombay

View Archive Info
 

Metadata

 
Field Value
 
Title Distinguishing chromatic number of random Cayley graphs
 
Names BALACHANDRAN, N
PADINHATTEERI, S
Date Issued 2017 (iso8601)
Abstract The distinguishing chromatic number of a graph G, denoted x(D)(G), is defined as the minimum number of colors needed to properly color G such that no non-trivial automorphism of G fixes each color class of G. In this paper, we consider random Cayley graphs Gamma defined over certain abelian groups A with vertical bar A vertical bar = n, and show that with probability at least 1 - n(-Omega(log n)), x(D)(Gamma) <= x(Gamma) + 1. (C) 2017 Elsevier B.V. All rights reserved.
Genre Article
Identifier DISCRETE MATHEMATICS,340(10)2447-2455