Dynamic chromatic number of regular graphs
Lists
Only you see this
Abstract
A k<math><mi is="true">k</mi></math>-dynamic coloring of a graph G<math><mi is="true">G</mi></math> is a proper coloring of G<math><mi is="true">G</mi></math> with k<math><mi is="true">k</mi></math> colors such that for every vertex v∈V(G)<math><mi is="true">v</mi><mo is="true">∈</mo><mi is="true">V</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math> of degree at least 2, the neighbors of v<math><mi is="true">v</mi></math> receive at least 2 colors. The dynamic chromatic number of a graph G<math><mi is="true">G</mi></math>, χ2(G)<math><msub is="true"><mrow is="true"><mi is="true">χ</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math>, is the least number k<math><mi is="true">k</mi></math> such that G<math><mi is="true">G</mi></math> admits a k<math><mi is="true">k</mi></math>-dynamic coloring. It was conjectured [B. Montgomery, Dynamic coloring of graphs, Ph.D. Thesis, West Virginia University, 2001.] that if G<math><mi is="true">G</mi></math> is a k<math><mi is="true">k</mi></math>-regular graph, then χ2(G)−χ(G)≤2<math><msub is="true"><mrow is="true"><mi is="true">χ</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">−</mo><mi is="true">χ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">≤</mo><mn is="true">2</mn></math>. In this paper, we prove that if G<math><mi is="true">G</mi></math> is a k<math><mi is="true">k</mi></math>-regular graph with χ(G)≥4<math><mi is="true">χ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">≥</mo><mn is="true">4</mn></math>, then χ2(G)≤χ(G)+α(G2)<math><msub is="true"><mrow is="true"><mi is="true">χ</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">≤</mo><mi is="true">χ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">+</mo><mi is="true">α</mi><mrow is="true"><mo is="true">(</mo><msup is="true"><mrow is="true"><mi is="true">G</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msup><mo is="true">)</mo></mrow></math>. It confirms the conjecture for all regular graphs with diameter at most 2<math><mn is="true">2</mn></math> and chromatic number at least 4<math><mn is="true">4</mn></math>. In fact, it shows that χ2(G)−χ(G)≤1<math><msub is="true"><mrow is="true"><mi is="true">χ</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">−</mo><mi is="true">χ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">≤</mo><mn is="true">1</mn></math> provided that G<math><mi is="true">G</mi></math> has diameter at most 2<math><mn is="true">2</mn></math> and χ(G)≥4<math><mi is="true">χ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">≥</mo><mn is="true">4</mn></math>. Moreover, we show that for any k<math><mi is="true">k</mi></math>-regular graph G<math><mi is="true">G</mi></math> with no induced C4<math><msub is="true"><mrow is="true"><mi is="true">C</mi></mrow><mrow is="true"><mn is="true">4</mn></mrow></msub></math>, χ2(G)−χ(G)≤2⌈4lnk+1⌉<math><msub is="true"><mrow is="true"><mi is="true">χ</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">−</mo><mi is="true">χ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">≤</mo><mn is="true">2</mn><mrow is="true"><mo is="true">⌈</mo><mn is="true">4</mn><mo is="true">ln</mo><mi is="true">k</mi><mo is="true">+</mo><mn is="true">1</mn><mo is="true">⌉</mo></mrow></math>. Also, we show that for any n<math><mi is="true">n</mi></math> there exists a regular graph G<math><mi is="true">G</mi></math> whose chromatic number is n<math><mi is="true">n</mi></math> and χ2(G)−χ(G)≥1<math><msub is="true"><mrow is="true"><mi is="true">χ</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">−</mo><mi is="true">χ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">≥</mo><mn is="true">1</mn></math>. This result gives a negative answer to a conjecture of Ahadi et al. [A. Ahadi, S. Akbari, A. Dehghan, M. Ghanbari, On the difference between chromatic number and dynamic chromatic number of graphs, Discrete Math. Available online 2011].
BibTeX
@article{alishahi2012dynamic,
author = {Meysam Alishahi},
title = {{Dynamic chromatic number of regular graphs}},
journal = {Discret. Appl. Math.},
year = {2012},
doi = {10.1016/j.dam.2012.05.017},
}Loading related content...