Mathematics – Combinatorics
Scientific paper
2009-11-21
Mathematics
Combinatorics
Upper Bounds for the Dynamic Chromatic Number of Graphs in Terms of the Independent Number
Scientific paper
A dynamic coloring of a graph $G$ is a proper coloring such that for every vertex $v\in V(G)$ of degree at least 2, the neighbors of $v$ receive at least 2 colors. The smallest integer $k$ such that $G$ has a dynamic coloring with $ k $ colors, is called the {\it dynamic chromatic number} of $G$ and denoted by $\chi_2(G)$. In this paper we will show that if $G$ is a regular graph, then $ \chi_{2}(G)- \chi(G) \leq 2\lfloor \log^{\alpha(G)}_{2}\rfloor +3 $ and if $G$ is a graph and $\delta(G)\geq 2$, then $ \chi_{2}(G)- \chi(G) \leq \lceil (4\Delta^{2})^{\frac{1}{\delta-1}} \rceil (\lfloor \log^{\alpha(G)}_{\frac{2\Delta(G)}{2\Delta(G)-\delta(G)}} \rfloor +1)+1 $ and in general case if $G$ is a graph, then $ \chi_{2}(G)- \chi(G) \leq 3+ \min \lbrace \alpha(G),\alpha^{\prime}(G),\frac{\alpha(G)+\omega(G)}{2}\rbrace $. At the end we will introduce a generalization of the Montgomery's Conjecture for the dynamic coloring of regular graphs.
Ahadi Arash
Dehghan Ali
No associations
LandOfFree
Upper Bounds for the Dynamic Chromatic Number of Graphs in Terms of the Independent Number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Upper Bounds for the Dynamic Chromatic Number of Graphs in Terms of the Independent Number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Upper Bounds for the Dynamic Chromatic Number of Graphs in Terms of the Independent Number will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-417838