Opuscula Math. 43, no. 1 (2023), 109-123

Opuscula Mathematica

On incidence coloring of graph fractional powers

Mahsa Mozafari-Nia
Moharram N. Iradmusa

Abstract. For any \(n\in \mathbb{N}\), the \(n\)-subdivision of a graph \(G\) is a simple graph \(G^\frac{1}{n}\) which is constructed by replacing each edge of \(G\) with a path of length \(n\). The \(m\)-th power of \(G\) is a graph, denoted by \(G^m\), with the same vertices of \(G\), where two vertices of \(G^m\) are adjacent if and only if their distance in \(G\) is at most \(m\). In [M.N. Iradmusa, On colorings of graph fractional powers, Discrete Math. 310 (2010), no. 10-11, 1551-1556] the \(m\)-th power of the \(n\)-subdivision of \(G\), denoted by \(G^{\frac{m}{n}}\) is introduced as a fractional power of \(G\). The incidence chromatic number of \(G\), denoted by \(\chi_i(G)\), is the minimum integer \(k\) such that \(G\) has an incidence \(k\)-coloring. In this paper, we investigate the incidence chromatic number of some fractional powers of graphs and prove the correctness of the incidence coloring conjecture for some powers of graphs.

Keywords: incidence coloring, incidence chromatic number, subdivision of graph, power of graph.

Mathematics Subject Classification: 05C15.

Full text (pdf)

  1. M. Behzad, Graphs and Their Chromatic Numbers, Ph.D. Thesis, Michigan State University, 1965.
  2. M. Bonamy, H. Hocquard, S. Kerdjoudj, A. Raspaud, Incidence coloring of graphs with high maximum average degree, Discrete Appl. Math. 227 (2017), 29-43. https://doi.org/10.1016/j.dam.2017.04.029
  3. J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, New York, 2008.
  4. R.A. Brualdi, J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993), 51-58. https://doi.org/10.1016/0012-365X(93)90286-3
  5. D. Chen, X. Liu, S. Wang, The incidence coloring number of graph and the incidence coloring conjecture, Math. Econom. (People's Republic of China) 15 (1998), 47-51.
  6. P. Gregor, B. Lužar, R. Soták, On incidence coloring conjecture in Cartesian products of graphs, Discrete Appl. Math. 213 (2016), 93-100. https://doi.org/10.1016/j.dam.2016.04.030
  7. P. Gregor, B. Lužar, R. Soták, Note on incidence chromatic number of subquartic graphs, J. Comb. Optim. 34 (2017), 174-181. https://doi.org/10.1007/s10878-016-0072-2
  8. B. Guiduli, On incidence coloring and star arboricity of graphs, Discrete Math. 163 (1997), 275-278.
  9. R. Hammack, W. Imrich, S. Klavzar, Handbook of Product Graphs, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2011.
  10. S. Hartke, H. Liu, S. Petrickova, On coloring of fractional powers of graphs, arxiv:1212.3898v1 (2013).
  11. M. Hosseini Dolama, E. Sopena, X. Zhu, Incidence coloring of \(k\)-degenerated graphs, Discrete Math. 283 (2004), 121-128. https://doi.org/10.1016/j.disc.2004.01.015
  12. M.N. Iradmusa, On colorings of graph fractional powers, Discrete Math. 310 (2010), 1551-1556. https://doi.org/10.1016/j.disc.2010.01.017
  13. M.N. Iradmusa, A short proof of 7-colorability of \(\frac{3}{3}\)-power of sub-cubic graphs, Iranian J. Sci. Tech., Transactions A: Sci. 44 (2020), no. 1, 225-226.
  14. H.J. Lai, B. Montgomery, H. Poon, Upper bounds of dynamic chromatic number, Ars Combin. 68 (2003), 193-201.
  15. D. Li, M. Liu, Incidence coloring of the squares of some graphs, Discrete Math. 308 (2008), 6569-6574. https://doi.org/10.1016/j.disc.2007.11.047
  16. M. Maydanskiy, The incidence coloring conjecture for graphs of maximum degree 3, Discrete Math. 292 (2005), 131-141. https://doi.org/10.1016/j.disc.2005.02.003
  17. B. Montgomery, Dynamic Coloring, Ph.D. Dissertation, West Virginia University, 2001.
  18. M. Mozafari-Nia, M.N. Iradmusa, A note on coloring of \(\frac{3}{3}\)-power of subquartic graphs, Australas. J. Combin. 79 (2021), 454-460.
  19. K. Nakprasit, K. Nakprasit, Incidence colorings of the powers of cycles, Int. J. Pure Appl. Math. 71 (2012), 143-148.
  20. K.J. Pai, J.M. Chang, J.S. Yang, R.U. Wu, Incidence coloring on hypercubes, Theor. Comput. Sci. 557 (2014), 59-65. https://doi.org/10.1016/j.tcs.2014.08.017
  21. K.J. Pai, J.M. Chang, J.S. Yang, R.U. Wu, On the incidence coloring number of folded hypercubes, 2014 International Computer Science and Engineering Conference (ICSEC), 7-11, 2014.
  22. W.C. Shiu, P.C.B. Lam, D.L. Chen, On incidence coloring for some cubic graphs, Discrete Math. 252 (2002), 259-266. https://doi.org/10.1016/S0012-365X(01)00457-5
  23. W.C. Shiu, P.K. Sun, Graphs which are not (\(\Delta+ 1\))-incidence colorable with erratum to the incidence chromatic number of outerplanar graphs, Technical Report of Department of Mathematics, Hong Kong Baptist University, 419 (2006), 397-405.
  24. P.K. Sun, W.C. Shiu, Some results on incidence coloring, star arboricity and domination number, Australas. J. Combin. 54 (2012), 107-114.
  25. F. Wang, X. Liu, Coloring 3-power of 3-subdivision of subcubic graph, Discrete Math. Algorithms and Appl. 10 (2018), 1850041. https://doi.org/10.1142/S1793830918500416
  26. S.D. Wang, D.L. Chen, S.C. Pang, The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Math. 256 (2002), 397-405. https://doi.org/10.1016/S0012-365X(01)00302-8
  27. S. Wang, J. Xu, F. Ma, C. Xu, The \((\Delta+2,2)\)-incidence coloring of outerplanar graphs, Progress in Natural Sci. 18 (2008), 575-578.
  28. J. Wu, Some results on the incidence coloring number of a graph, Discrete Math. 309 (2009), 3866-3870. https://doi.org/10.1016/j.disc.2008.10.027
  29. D. Yang, Fractional incidence coloring and star arboricity of graphs, Ars Combin. 105 (2012), 213-224.
  • Mahsa Mozafari-Nia
  • Shahid Beheshti University, Department of Mathematical Sciences, G.C. P.O. Box 19839-63113, Tehran, Iran
  • Moharram N. Iradmusa (corresponding author)
  • ORCID iD https://orcid.org/0000-0003-0608-5781
  • Shahid Beheshti University, Department of Mathematical Sciences, G.C. P.O. Box 19839-63113, Tehran, Iran
  • Communicated by Adam Paweł Wojda.
  • Received: 2022-01-26.
  • Revised: 2022-11-16.
  • Accepted: 2022-11-22.
  • Published online: 2022-12-30.
Opuscula Mathematica - cover

Cite this article as:
Mahsa Mozafari-Nia, Moharram N. Iradmusa, On incidence coloring of graph fractional powers, Opuscula Math. 43, no. 1 (2023), 109-123, https://doi.org/10.7494/OpMath.2023.43.1.109

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

We advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.