Achromatic and Harmonious Colorings of Circulant Graphs. Issue 1 (22nd February 2017)

• Record Type: Journal Article
• Authors: Dębski, Michał; Lonc, Zbigniew; Rzążewski, Paweł
• Is Part Of: Journal of graph theory. Volume 87:Issue 1(2018)
• Page Start: 18
• Page End: 34
• Publication Date: 2017-02-22
• Subjects: achromatic number -- harmonious chromatic number -- circulant graph -- k‐radius sequence; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22137
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A proper vertex coloring of a graph G is achromatic (respectively harmonious ) if every two colors appear together on at least one (resp. at most one) edge. The largest (resp. the smallest) number of colors in an achromatic (resp. a harmonious) coloring of G is called the achromatic (resp. harmonious chromatic ) number of G and denoted by ψ ( G ) (resp. h ( G ) ). For a finite set of positive integers D and a positive integer n, a circulant graph, denoted by C n D, is an undirected graph on the set of vertices { 0, 1, …, n − 1 } that has an edge i j if and only if either i − j or j − i is a member of D (where substraction is computed modulo n ). For any fixed set D, we show that ψ ( C n D ) is asymptotically equal to 2 D n, with the error term O ( log n ) . We also prove that h ( C n D ) is asymptotically equal to 2 D n, with the error term O ( n 1 4 log n ) . As corollaries, we get results that improve, for a fixed k, the previously best estimations on the lengths of a shortest k ‐radius sequence over an n ‐ary alphabet (i.e., a sequence in which any two distinct elements of the alphabet occur within distance k of each other) and a longest packing k ‐radius sequence over an n ‐ary alphabet (which is a dual counterpart of a k ‐radius sequence).