Opuscula Math. 43, no. 1 (2023), 109-123
https://doi.org/10.7494/OpMath.2023.43.1.109
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.
- M. Behzad, Graphs and Their Chromatic Numbers, Ph.D. Thesis, Michigan State University, 1965.
- 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
- J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, New York, 2008.
- 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
- 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.
- 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
- 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
- B. Guiduli, On incidence coloring and star arboricity of graphs, Discrete Math. 163 (1997), 275-278.
- 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.
- S. Hartke, H. Liu, S. Petrickova, On coloring of fractional powers of graphs, arxiv:1212.3898v1 (2013).
- 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
- 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
- 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.
- H.J. Lai, B. Montgomery, H. Poon, Upper bounds of dynamic chromatic number, Ars Combin. 68 (2003), 193-201.
- 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
- 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
- B. Montgomery, Dynamic Coloring, Ph.D. Dissertation, West Virginia University, 2001.
- 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.
- K. Nakprasit, K. Nakprasit, Incidence colorings of the powers of cycles, Int. J. Pure Appl. Math. 71 (2012), 143-148.
- 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
- 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.
- 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
- 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.
- P.K. Sun, W.C. Shiu, Some results on incidence coloring, star arboricity and domination number, Australas. J. Combin. 54 (2012), 107-114.
- 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
- 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
- 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.
- 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
- 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)
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.
