2014/01/24 by Ali Taherkhani, Taherkhani, Ali
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1401.6470
9 pages
arxiv created 2014/01/24 · openalex publication_date 2014/01/24 · arxiv updated 2014/01/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An r-dynamic k-coloring of a graph G is a proper vertex k-coloring such that the neighbors of any vertex v receive at least min\r,\rm deg(v)\ different colors. The r-dynamic chromatic number of G, χr(G), is defined as the smallest k such that G admits an r-dynamic k-coloring. In this paper we introduce an upper bound for χr(G) in terms of r, chromatic number, maximum degree and minimum degree. In 2001, Montgomery \citeMR2702379 conjectured that, for a d-regular graph G, χ2(G)-χ(G)≤ 2. In this regard, for a d-regular graph G, we present two upper bounds for χ2(G)-χ(G), one of them, \lceil 5.437log d+2.721\rceil, is an improvement of the bound 14.06log d +1, proved by Alishahi (2011) \citeMR2746973. Also, we give an upper bound for χ2(G) in terms of chromatic number, maximum degree and minimum degree.