BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The \textit{Distinguishing Chromatic Number} of a graph G, denoted χ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 ϕ of the graph G fixes each color class of G. In this paper, we consider random Cayley graphs Γ(A,S) defined over certain abelian groups A and show that with probability at least 1−n−Ω(logn) we have, χD(Γ)≤χ(Γ)+1.
A graph G is said to be k-distinguishable if the vertex set can be colored using k colors such that no non-trivial automorphism fixes every color class, and the distinguishing number D(G) is the least integer k for which G is k-distinguishable. If for each v∈V(G) we have a list L(v) of colors, and we stipulate that the color assigned to vertex v comes from its list L(v) then G is said to be L-distinguishable where L={L(v)}v∈V(G). The list distinguishing number of a graph, denoted Dl(G), is the minimum integer k such that every collection of lists L with ∣L(v)∣=k admits an L-distinguishing coloring. In this paper, we prove that Dl(G)=D(G) when G is a Kneser graph.
The \textit{Distinguishing Chromatic Number} of a graph G, denoted χ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 ϕ of the graph G fixes each color class of G. In this paper, 1. We prove a lemma that may be considered a variant of the Motion lemma of \cite{RS} and use this to give examples of several families of graphs which satisfy χD(G)=χ(G)+1. 2.We give an example of families of graphs that admit large automorphism groups in which every proper coloring is distinguishing. We also describe families of graphs with (relatively) very small automorphism groups which satisfy χD(G)=χ(G)+1, for arbitrarily large values of χ(G). 3. We describe non-trivial families of bipartite graphs that satisfy χD(G)>r for any positive integer r.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.