Opuscula Math. 40, no. 4 (2020), 475-482
https://doi.org/10.7494/OpMath.2020.40.4.475

Opuscula Mathematica

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

Július Czap

Abstract. 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 $$\text{erb}(G)$$. Trivially, $$\text{erb}(G) \geq \text{L}(G)+1$$ holds for every plane graph without cut-vertices, where $$\text{L}(G)$$ denotes the length of a longest facial path in $$G$$. Jendroľ in 2018 proved that every simple $$3$$-connected plane graph admits a facial rainbow edge-coloring with at most $$\text{L}(G)+2$$ colors, moreover, this bound is tight for $$\text{L}(G)=3$$. He also proved that $$\text{erb}(G) = \text{L}(G)+1$$ for $$\text{L}(G)\not\in\{3,4,5\}$$. He posed the following conjecture: There is a simple $$3$$-connected plane graph $$G$$ with $$\text{L}(G)=4$$ and $$\text{erb}(G)=\text{L}(G)+2$$. In this note we answer the conjecture in the affirmative.

Keywords: plane graph, facial path, edge-coloring.

Mathematics Subject Classification: 05C10, 05C15.

Full text (pdf)

1. D.W. Barnette, B. Grünbaum, 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. 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. P. Erdős, 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. Jendroľ, 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 $$\Delta=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 über 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.
• Július Czap
• https://orcid.org/0000-0002-9933-5884
• Technical University of Košice, Faculty of Economics, Department of Applied Mathematics and Business Informatics, Němcovej 32, 040 01 Košice, Slovakia
• Communicated by Adam Paweł Wojda.
• Revised: .
• Accepted: 2020-04-26.
• Published online: 2020-07-09.