Facial graceful coloring of plane graphs

• Autorzy: Czap Július

Identyfikatory

DOI

10.7494/OpMath.2024.44.6.815

• Języki publikacji: EN

Abstrakty

EN

Let G be a plane graph. Two edges of G are facially adjacent if they are consecutive on the boundary walk of a face of G. A facial edge coloring of G is an edge coloring such that any two facially adjacent edges receive different colors. A facial graceful k-coloring of G is a proper vertex coloring c : V (G) → {1, 2, . . . , k} such that the induced edge coloring c′ : E(G) → {1, 2, . . . , k−1} defined by c′(uv) = |c(u)−c(v)| is a facial edge coloring. The minimum integer k for which G has a facial graceful k-coloring is denoted by χfg(G). In this paper we prove that χfg(G) ≤ 14 for every plane graph G and χfg(H) ≤ 9 for every outerplane graph H. Moreover, we give exact bounds for cacti and trees.

Słowa kluczowe

EN

facial edge coloring; plane graph

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2024
• Tom: Vol. 44, no. 6
• Strony: 815--825
• Opis fizyczny: Bibliogr. 20 poz., rys., tab.

Twórcy

autor

Czap Július

• Technical University of Košice, Faculty of Economics, Department of Applied Mathematics and Business Informatics, Němcovej 32, 040 01 Košice, Slovakia

• https://orcid.org/0000-0002-9933-5884

Bibliografia

• [1] M.L. Asy’ari, Dafik, I.H. Agustin, R. Nisviasari, R. Adawiyah, On graceful chromatic number of some graphs, J. Phys.: Conf. Ser. 2157 (2022), 012013.
• [2] R. Alfarisi, Dafik, R.M. Prihandini, R. Adawiyah, E.R. Albirri, I.H. Agustin, Graceful chromatic number of unicyclic graphs, J. Phys.: Conf. Ser. 1306 (2019), 012039.
• [3] Z. Bi, A. Byers, S. English, E. Laforge, P. Zhang, Graceful colorings of graphs, J. Combin. Math. Combin. Comput. 101 (2017), 101–119.
• [4] Z. Bi, A. Byers, P. Zhang, Revisiting graceful labelings of graphs, J. Combin. Math. Combin. Comput. 102 (2017), 141–158.
• [5] J. Czap, S. Jendroľ, Facially-constrained colorings of plane graphs: a survey, Discrete Math. 340 (2017), 2691–2703.
• [6] J. Czap, S. Jendroľ, Facial colorings of plane graphs, J. Interconnect. Netw. 19 (2019), 1940003.
• [7] S. English, P. Zhang, On graceful colorings of trees, Math. Bohem. 142 (2017), 57–73.
• [8] P. Erdős, P. Turán, On some sequences of integers, J. Lond. Math. Soc. 11 (1936), no. 4, 261–264.
• [9] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2023), #DS6.
• [10] S. Khoirunnisa, Dafik, A.I. Kristiana, R. Alfarisi, E.R. Albirri, On graceful chromatic number of comb product of ladder graph, J. Phys.: Conf. Ser. 1836 (2021), 012027.
• [11] D. Kráľ, T. Madaras, R. Škrekovski, Cyclic, diagonal and facial colorings, European J. Combin. 26 (2005), 473–490.
• [12] A.I. Kristiana, D. Setyawan, E.R. Albirri, R.M. Prihandini, R. Alfarisi, On graceful coloring of generalized Petersen graphs, Discrete Math. Algorithms Appl. (2023), 2350097.
• [13] D. Laavanya, S.D. Yamini, A structural approach to the graceful coloring of a subclass of trees, Heliyon 9 (2023), e19563.
• [14] R. Mincu, C. Obreja, A. Popa, The graceful chromatic number for some particular classes of graphs, Int. Symp. SYNASC (2019), 109–115.
• [15] M. Montassier, A. Raspaud, A note on 2-facial coloring of plane graphs, Inform. Process. Lett. 98 (2006), 235–241.
• [16] C. Obreja, Results on graceful chromatic number for particular graphs, Int. Symp. SYNASC (2020), 109–116.
• [17] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Int. Symp. Rome 1966), (1967), 349–355.
• [18] T.L. Saaty, P.C. Kainen, The Four-Color Problem, Assaults and Conquest, McGraw-Hill, London, 1977.
• [19] I.N. Suparta, Y. Lin, R. Hasni, I.N. Budayana, On odd-graceful coloring of graphs, Commun. Comb. Optim. (2023).
• [20] I.N. Suparta, M. Venkathacalam, I.G.A. Gunadi, P.A.C. Pratama, Graceful chromatic number of some Cartesian product graphs, Ural Math. J. 9 (2023), 193–208.

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)