On -dynamic coloring of graphs

详细信息    查看全文

• 作者：Sogol Jahanbekam^a ; ^{sogol.jahanbekam@ucdenver.edu" class="auth_mail" title="E-mail the corresponding author} ; Jaehoon Kim^b ; ^{kimJS@bham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Suil O^c ; ^{osuilo@sfu.ca" class="auth_mail" title="E-mail the corresponding author} ; Douglas B. West^d ; ^e ; ^{dwest@math.uiuc.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Dynamic coloring ; Graph coloring
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：19 June 2016
• 年：2016
• 卷：206
• 期：Complete
• 页码：65-72
• 全文大小：383 K

文摘

An r$r$-dynamic proper  k$k$-coloring   of a graph abf3134682e1d846ffeabf37a1cf" title="Click to view the MathML source">G$G$ is a proper k$k$-coloring of abf3134682e1d846ffeabf37a1cf" title="Click to view the MathML source">G$G$ such that every vertex in bf32be91c911ac74f72" title="Click to view the MathML source">V(G)$V\left(G\right)$ has neighbors in at least min{d(v),r}$min\{d\left(v\right),r\}$ different color classes. The r$r$-dynamic chromatic number   of a graph abf3134682e1d846ffeabf37a1cf" title="Click to view the MathML source">G$G$, written χ_r(G)${\chi }_r\left(G\right)$, is the least k$k$ such that abf3134682e1d846ffeabf37a1cf" title="Click to view the MathML source">G$G$ has such a coloring. By a greedy coloring algorithm, χ_r(G)≤rΔ(G)+1${\chi }_r\left(G\right)\le r\Delta \left(G\right)+1$; we prove that equality holds for Δ(G)>2$\Delta \left(G\right)>2$ if and only if abf3134682e1d846ffeabf37a1cf" title="Click to view the MathML source">G$G$ is r$r$-regular with diameter 2 and girth 5. We improve the bound to χ_r(G)≤Δ(G)+2r−2${\chi }_r\left(G\right)\le \Delta \left(G\right)+2r-2$ when δ(G)>2rlnn$\delta \left(G\right)>2rlnn$ and χ_r(G)≤Δ(G)+r${\chi }_r\left(G\right)\le \Delta \left(G\right)+r$ when δ(G)>r²lnn$\delta \left(G\right)>r^{2}lnn$.

In terms of the chromatic number, we prove χ_r(G)≤rχ(G)${\chi }_r\left(G\right)\le r\chi \left(G\right)$ when abf3134682e1d846ffeabf37a1cf" title="Click to view the MathML source">G$G$ is k$k$-regular with k≥(3+o(1))rlnr$k\ge (3+o\left(1\right))rlnr$ and show that χ_r(G)${\chi }_r\left(G\right)$ may exceed r^1.377χ(G)$r^{1.377}\chi \left(G\right)$ when k=r$k=r$. We prove χ₂(G)≤χ(G)+2${\chi }_2\left(G\right)\le \chi \left(G\right)+2$ when abf3134682e1d846ffeabf37a1cf" title="Click to view the MathML source">G$G$ has diameter 2, with equality only for complete bipartite graphs and the 5-cycle. Also, χ₂(G)≤3χ(G)${\chi }_2\left(G\right)\le 3\chi \left(G\right)$ when abf3134682e1d846ffeabf37a1cf" title="Click to view the MathML source">G$G$ has diameter 3, which is sharp. However, χ₂${\chi }_2$ is unbounded on bipartite graphs with diameter 4, and bf3" title="Click to view the MathML source">χ₃${\chi }_3$ is unbounded on bipartite graphs with diameter 3 or 3-colorable graphs with diameter 2. Finally, we study χ_r${\chi }_r$ on grids and toroidal grids.