Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Czasopismo
Rocznik
Tom
Strony
475--482
Opis fizyczny
Bibliogr. 32 poz.
Twórcy
autor
- 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-371a7b68-992e-42c5-8c86-f868aa8e2941