On incidence coloring of graph fractional powers

• Autorzy: Mozafari-Nia Mahsa , Iradmusa Moharram N.

Identyfikatory

DOI

10.7494/OpMath.2023.43.1.109

• Języki publikacji: EN

Abstrakty

EN

For any n ∈ N, the n-subdivision of a graph G is a simple graph G 1n 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 Gm, with the same vertices of G, where two vertices of Gm 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 Gm n is introduced as a fractional power of G. The incidence chromatic number of G, denoted by χ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.

Słowa kluczowe

EN

incidence coloring; incidence chromatic number; subdivision of graph; power of graph

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2023
• Tom: Vol. 43, no. 1
• Strony: 109--123
• Opis fizyczny: Bibliogr. 29 poz.

Twórcy

autor

Mozafari-Nia Mahsa

• Shahid Beheshti University, Department of Mathematical Sciences, G.C. P.O. Box 19839-63113, Tehran, Iran

autor

Iradmusa Moharram N.

• Shahid Beheshti University, Department of Mathematical Sciences, G.C. P.O. Box 19839-63113, Tehran, Iran

• https://orcid.org/0000-0003-0608-5781

Bibliografia

• [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.
• [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.
• [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.
• [7] P. Gregor, B. Lužar, R. Soták, Note on incidence chromatic number of subquartic graphs, J. Comb. Optim. 34 (2017), 174–181.
• [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.
• [12] M.N. Iradmusa, On colorings of graph fractional powers, Discrete Math. 310 (2010), 1551–1556.
• [13] M.N. Iradmusa, A short proof of 7-colorability of 33-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.
• [16] M. Maydanskiy, The incidence coloring conjecture for graphs of maximum degree 3, Discrete Math. 292 (2005), 131–141.
• [17] B. Montgomery, Dynamic Coloring, Ph.D. Dissertation, West Virginia University, 2001.
• [18] M. Mozafari-Nia, M.N. Iradmusa, A note on coloring of 33-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.
• [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.
• [23] W.C. Shiu, P.K. Sun, Graphs which are not (Δ + 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.
• [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.
• [27] S. Wang, J. Xu, F. Ma, C. Xu, The (Δ + 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.
• [29] D. Yang, Fractional incidence coloring and star arboricity of graphs, Ars Combin. 105 (2012), 213–224.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)