Opuscula Mathematica
Opuscula Math. 40, no. 4 (2020), 475-482

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)
References ▼
  1. [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. [2] J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, 2008.
  3. [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. [4] Y. Cao, G. Chen, G. Jing, M. Stiebitz, B. Toft, Graph edge coloring: A survey, Graphs Combin. 35 (2019), 33-66.
  5. [5] J. Czap, S. Jendroľ, Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017), 2691-2703.
  6. [6] J. Czap, S. Jendroľ, Facial colorings of plane graphs, J. Interconnect. Netw. 19 (2019), 1940003.
  7. [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. [8] J. Richter-Gebert, Realization Spaces of Polytopes, Springer, 1996.
  9. [9] J.L. Gross, T.W. Tucker, Topological Graph Theory, Dover Publications, 2001.
  10. [10] Z. Guofei, A note on graphs of class I, Discrete Math. 263 (2003), 339-345.
  11. [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. [12] I. Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 10 (1981), 718-720.
  13. [13] D. Huang, W. Wang, Planar graphs of maximum degree six without 7-cycles are class one, Electron. J. Combin. 19 (2012), #P17.
  14. [14] S. Jendroľ, Facial rainbow edge-coloring of plane graphs, Graphs Combin. 34 (2018), 669-676.
  15. [15] B. Mohar, C. Thomassen, Graphs on surfaces, The John Hopkins University Press, 2001.
  16. [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. [17] W. Ni, Edge colorings of planar graphs without adjacent special cycles, Ars Combin. 105 (2012), 247-256.
  18. [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. [19] A.B. Owens, On the planarity of regular incidence sequences, J. Combin. Theory 11 (1971), 201-212.
  20. [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. [21] E. Steinitz, H. Rademacher, Vorlesungen über die Theorie der Polyeder, Springer-Verlag, 1976.
  22. [22] W.T. Tutte, A theory of 3-connected graphs, Indag. Math. 23 (1961), 441-455.
  23. [23] V.G. Vizing, On an estimate of the chromatic class of a \(p\)-graph, Diskret. Analiz 3 (1964), 25-30.
  24. [24] V.G. Vizing, Critical graphs with a given chromatic class, Metody Diskret. Analiz. 5 (1965), 9-17.
  25. [25] W. Wang, Y. Chen, A sufficient condition for a planar graph to be class 1, Theoret. Comput. Sci. 385 (2007), 71-77.
  26. [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. [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. [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. [29] L. Zhang, Every planar graph with maximum degree 7 is class I, Graphs Combin. 16 (2000), 467-495.
  30. [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. [31] W. Zhang, J.-L. Wu, Edge coloring of planar graphs without adjacent 7-cycles, Theoret. Comput. Sci. 739 (2018), 59-64.
  32. [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.
About the authors ▼
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
About the article ▼
Communicated by Adam Paweł Wojda.
Received: 2019-12-27.
Revised: .
Accepted: 2020-04-26.
Published online: 2020-07-09.
Cite this article as ▼
Július Czap, Facial rainbow edge-coloring of simple 3-connected plane graphs, Opuscula Math. 40, no. 4 (2020), 475-482, https://doi.org/10.7494/OpMath.2020.40.4.475.
Download this article's citation as: