Published in Volume XXVI, Issue 2, 2016, pages 249–261, doi: 10.7561/SACS.2016.2.249

Authors: S. Saqaeeyan, E. Mollaahamdi

Abstract

A dynamic coloring of a graph G is a proper vertex coloring such that for every vertex v ∈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 dynamic chromatic number of G and denoted by χ2(G). Montgomery conjectured that for every r-regular graph G, χ2(G)-χ(G) ≤ 2 . Finding an optimal upper bound for χ2(G)-χ(G) seems to be an intriguing problem. We show that there is a constant d such that every bipartite graph G with δ(G) ≥ d , has χ2(G)-χ(G) ≤ 2⌈(Δ(G))/(δ(G))⌉. It was shown that χ2(G)-χ(G) ≤ α’ (G) +k* [2]. Also, χ2(G)-χ(G) ≤ α(G) +k* [1]. We prove that if G is a simple graph with δ(G)>2, then χ2(G)-χ(G) ≤ (α’ (G)+w(G) )/2 +k* . Among other results, we prove that for a given bipartite graph G=[X,Y], determining whether G has a dynamic 4-coloring l : V (G)→{a, b, c, d} such that a, b are used for part X and c, d are used for part Y is NP-complete.

Full Text (PDF)

References

[1] A. Ahadi, S. Akbari, A. Dehghan, and M. Ghanbari. On the difference between chromatic number and dynamic chromatic number of graphs. Discrete Mathematics, 312(17):2579–2583, 2012. doi:10.1016/j.disc.2011.09.006.

[2] A. Ahadi and A. Dehghan. Upper bounds for the 2-hued chromatic number of graphs in terms of the independence number. Discrete Applied Mathematics, 160(15):2142–2146, 2012. doi:10.1016/j.dam.2012.05.003.

[3] A. Ahadi and A. Dehghan. The complexity of the proper orientation number. Information Processing Letters, 113(19-21):799–803, 2013. doi:10.1016/j.ipl.2013.07.017.

[4] A. Ahadi, A. Dehghan, and M.-R. Sadeghi. Algorithmic complexity of proper labeling problems. Theoretical Computer Science, 495:25–36, 2013. doi:10.1016/j.tcs.2013.05.027.

[5] S. Akbari, M. Ghanbari, and S. Jahanbekam. On the list dynamic coloring of graphs. Discrete Applied Mathematics, 157(14):3005–3007, 2009. doi: 10.1016/j.dam.2009.05.002.

[6] S. Akbari, M. Ghanbari, and S. Jahanbekam. On the dynamic chromatic number of graphs. In Combinatorics and graphs, volume 531 of Contemp. Math., pages 11–18. Amer. Math. Soc., Providence, RI, 2010. doi:10.1090/conm/531/10454.

[7] M. Alishahi. On the dynamic coloring of graphs. Discrete Applied Mathematics, 159(2-3):152–156, 2011. doi:10.1016/j.dam.2010.10.012.

[8] M. Alishahi. Dynamic chromatic number of regular graphs. Discrete Applied Mathematics, 160(15):2098–2103, 2012. doi:10.1016/j.dam.2012.05.017.

[9] N. Alon and J. H. Spencer. The probabilistic method. Wiley- Interscience Series in Discrete Mathematics and Optimization. Wiley- Interscience [John Wiley & Sons], New York, second edition, 2000.

[10] Y. Chen, S. Fan, H.-J. Lai, H. Song, and L. Sun. On dynamic coloring for planar graphs and graphs of higher genus. Discrete Applied Mathematics, 160(7–8):1064–1071, 2012. doi:10.1016/j.dam.2012.01.012.

[11] A. Dehghan. On strongly planar not-all-equal 3SAT. Journal of Combinatorial Optimization, 32(3):721–724, 2016. doi:10.1007/s10878-015-9894-6.

[12] A. Dehghan, M.-R. Sadeghi, and A. Ahadi. On the complexity of deciding whether the regular number is at most two. Graphs and Combinatorics, 31(5):1359–1365, 2015. doi:10.1007/s00373-014-1446-9.

[13] L. Esperet. Dynamic list coloring of bipartite graphs. Discrete Applied Mathematics, 158(17):1963–1965, 2010. doi:10.1016/j.dam.2010.08.007.

[14] S.-J. Kim, S. J. Lee, and W.-J. Park. Dynamic coloring and list dynamic coloring of planar graphs. Discrete Applied Mathematics, 161(13–14):2207–2212, 2013. doi:10.1016/j.dam.2013.03.005.

[15] H.-J. Lai, J. Lin, B. Montgomery, T. Shui, and S. Fan. Conditional colorings of graphs. Discrete Mathematics, 306(16):1997–2004, 2006. doi:10.1016/j.disc.2006.03.052.

[16] H.-J. Lai, B. Montgomery, and H. Poon. Upper bounds of dynamic chromatic number. Ars Combinatoria, 68:193–201, 2003.

[17] X. Li and W. Zhou. The 2nd-order conditional 3-coloring of claw- free graphs. Theoretical Computer Science, 396(17):151–157, 2008. doi:10.1016/j.tcs.2008.01.034.

[18] X. Li, X. Yao, W. Zhou, and H. Broersma. Complexity of conditional colorability of graphs. Applied Mathematics Letters, 22(3):320–324, 2009. doi:10.1016/j.aml.2008.04.003.

[19] B. Montgomery. Dynamic Coloring of Graphs. Ph.D. Dissertation, West Virginia University, 2001.

[20] B. M. Moret. Planar NAE3SAT is in P. SIGACT News 19, 2, pages 51–54, 1988. doi:10.1145/49097.49099.

[21] A. Taherkhani. On r-dynamic chromatic number of graphs. Discrete Applied Mathematics, 201:222–227, 2016. doi:10.1016/j.dam.2015.07.019.

[22] C. Thomassen. The even cycle problem for directed graphs. Journal of the American Mathematical Society, 5(2):217–229, 1992. doi:10.2307/2152767.

[23] D. B. West. Introduction to graph theory. Prentice Hall Inc., Upper Saddle River, NJ, 1996.

Bibtex

@article{sacscuza:saqaeeyan2016dcnobg,
  title={Dynamic Chromatic Number of Bipartite Graphs},
  author={S. Saqaeeyan and E. Mollaahamdi},
  journal={Scientific Annals of Computer Science},
  volume={26},
  number={2},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2016},
  pages={249–261},
  doi={ 10.7561/SACS.2016.2.249},
  publisher={``A.I. Cuza'' University Press}
}