Facial rainbow edge-coloring of simple 3-connected plane graphs

• Autorzy: Czap Julius

Identyfikatory

DOI

10.7494/OpMath.2020.40.4.475

• Języki publikacji: EN

Abstrakty

EN

A facial rainbow edge-coloring of a plane graph G is an edge-coloring such that any two edges receive distinct colors if they lie on a common facial path of G. The minimum number of colors used in such a coloring is denoted by erb(G). Trivially, erb(G) ≥ L(G) + 1 holds for every plane graph without cut-vertices, where L(G) denotes the length of a longest facial path in G. Jendrol’ in 2018 proved that every simple 3-connected plane graph admits a facial rainbow edge-coloring with at most L(G) + 2 colors, moreover, this bound is tight for L(G) = 3. He also proved that erb(G) = L(G) + 1 for L(G) ∉ {3,4, 5}. He posed the following conjecture: There is a simple 3-connected plane graph G with L(G) = 4 and erb(G) = L(G) + 2. In this note we answer the conjecture in the affirmative. Keywords: plane graph, facial path, edge-coloring.

Słowa kluczowe

EN

plane graph; facial path; edge-coloring

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2020
• Tom: Vol. 40, no. 4
• Strony: 475--482
• Opis fizyczny: Bibliogr. 32 poz.

Twórcy

autor

Czap Julius

• Technical University of Kosice Faculty of Economics Department of Applied Mathematics and Business Informatics Nemcovej 32, 040 01 Kosice, Slovakia

Bibliografia

• [1] D.W. Barnette, B. Grunbaum, On Steinitz's theorem concerning convex 3-polytopes and on some properties of 3-connected planar graphs, [in:] The many facets of graph theory, Lecture Notes in Mathematics, 1969, 27-40.
• [2] J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, 2008.
• [3] Y. Bu, W. Wang, Some sufficient conditions for a planar graph of maximum degree six to be class 1, Discrete Math. 306 (2006), 1440-1445.
• [4] Y. Cao, G. Chen, G. Jing, M. Stiebitz, B. Toft, Graph edge coloring: A survey, Graphs Combin. 35 (2019), 33-66.
• [5] J. Czap, S. Jendrol', Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017), 2691-2703.
• [6] J. Czap, S. Jendrol', Facial colorings of plane graphs, J. Interconnect. Netw. 19 (2019), 1940003.
• [7] P. Erdos, R.J. Wilson, On the chromatic index of almost all graphs, J. Combin. Theory Ser. B 23 (1977), 255-257.
• [8] J. Richter-Gebert, Realization Spaces of Polytopes, Springer, 1996. [9] J.L. Gross, T.W. Tucker, Topological Graph Theory, Dover Publications, 2001. [10] Z. Guofei, A note on graphs of class I, Discrete Math. 263 (2003), 339-345.
• [11] M. Hasheminezhad, B.D. McKay, T. Reeves, Recursive generation of simple planar 5-regular graphs and pentangulations, J. Graph Algorithms Appl. 15 (2011), 417-436.
• [12] I. Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 10 (1981), 718-720.
• [13] D. Huang, W. Wang, Planar graphs of maximum degree six without 7-cycles are class one, Electron. J. Combin. 19 (2012), #P17.
• [14] S. Jendrol', Facial rainbow edge-coloring of plane graphs, Graphs Combin. 34 (2018), 669-676.
• [15] B. Mohar, C. Thomassen, Graphs on surfaces, The John Hopkins University Press, 2001.
• [16] W. Ni, Edge colorings of planar graphs with A = 6 without short cycles contain chords, J. Nanjing Norm. Univ. 34 (2011), 19-24.
• [17] W. Ni, Edge colorings of planar graphs without adjacent special cycles, Ars Combin. 105 (2012), 247-256.
• [18] W.-P. Ni, J.-L. Wu, Edge coloring of planar graphs which any two short cycles are adjacent at most once, Theoret. Comput. Sci. 516 (2014), 133-138.
• [19] A.B. Owens, On the planarity of regular incidence sequences, J. Combin. Theory 11 (1971), 201-212.
• [20] D.P. Sanders, Y. Zhao, Planar graphs of maximum degree seven are class I, J. Combin. Theory Ser. B 83 (2001), 201-212.
• [21] E. Steinitz, H. Rademacher, Vorlesungen iiber die Theorie der Polyeder, Springer-Verlag, 1976.
• [22] W.T. Tutte, A theory of 3-connected graphs, Indag. Math. 23 (1961), 441-455.
• [23] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz 3 (1964), 25-30.
• [24] V.G. Vizing, Critical graphs with a given chromatic class, Metody Diskret. Analiz. 5 (1965), 9-17.
• [25] W. Wang, Y. Chen, A sufficient condition for a planar graph to be class 1, Theoret. Comput. Sci. 385 (2007), 71-77.
• [26] Y. Wang, L. Xu, A sufficient condition for a plane graph with maximum degree 6 to be class 1, Discrete Appl. Math. 161 (2013), 307-310.
• [27] J.-L. Wu, L. Xue, Edge colorings of planar graphs without 5-cycles with two chords, Theoret. Comput. Sci. 518 (2014), 124-127.
• [28] L. Xue, J. Wu, Edge colorings of planar graphs without 6-cycles with two chords, Open J. Discrete Math. 3 (2013), 83-85.
• [29] L. Zhang, Every planar graph with maximum degree 7 is class I, Graphs Combin. 16 (2000), 467-495.
• [30] W. Zhang, J.-L. Wu, A note on the edge colorings of planar graphs without 7-cycles with three chords, Ars Combin. 138 (2018), 393-402.
• [31] W. Zhang, J.-L. Wu, Edge coloring of planar graphs without adjacent 7-cycles, Theoret. Comput. Sci. 739 (2018), 59-64.
• [32] W. Zhang, J.-L. Wu, Edge colorings of planar graphs without 6-cycles with three chords, Bull. Malays. Math. Sci. Soc. 41 (2018), 1077-1084.

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).