On -dynamic chromatic number of graphs

详细信息    查看全文

• 作者：Ali Taherkhani ^{ali.taherkhani@iasbs.ac.ir" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Chromatic number ; rr-dynamic chromatic number ; Forest transversal
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：11 March 2016
• 年：2016
• 卷：201
• 期：Complete
• 页码：222-227
• 全文大小：364 K

文摘

An r$r$-dynamic k$k$-coloring of a graph G$G$ is a proper vertex k$k$-coloring of G$G$ such that the neighbors of any vertex v$v$ receive at least min{r,deg(v)}$min\{r,deg\left(v\right)\}$ different colors. The r$r$-dynamic chromatic number of G$G$, χ_r(G)${\chi }_r\left(G\right)$, is defined as the smallest k$k$ such that G$G$ admits an r$r$-dynamic k$k$-coloring. In this paper, first we introduce an upper bound for χ_r(G)${\chi }_r\left(G\right)$ in terms of r$r$, chromatic number, maximum degree and minimum degree. Then, motivated by a conjecture of Montgomery (2001) stating that for a 22e8" title="Click to view the MathML source">d$d$-regular graph G$G$, χ₂(G)−χ(G)≤2${\chi }_2\left(G\right)-\chi \left(G\right)\le 2$, we prove two upper bounds for χ₂−χ${\chi }_2-\chi$ on regular graphs. Our first upper bound e6714ce102" title="Click to view the MathML source">⌈5.437logd+2.721⌉$\lceil 5.437logd+2.721\rceil$ improves a result of Alishahi (2011). Also, our second upper bound shows that Montgomery’s conjecture is implied by the existence of a χ(G)$\chi \left(G\right)$-coloring for any regular graph G$G$, such that any two vertices whose neighbors are unicolored in this coloring, have no common neighbor.