Weakly edge-face coloring of Halin graphs

Abstract

Let G=(V,E,F) be a connected loopless plane graph, with vertex set V, edge set E, and face set F. For any adjacent faces e₁ and e₂, if they are incident to the same face and appear consecutively on the edge of that face, then it is said that e₁ and e₂ are facially adjacent. A plane graph G is called weakly edge-face k-colorable indicating that there is a mapping \pi :E\cup F\to\{1,2,\dots ,k\} such that any two incident edges and faces, adjacent faces, and facially adjacent edges receive distinct colors. The weakly edge-face chromatic number of G, denoted by {\overline{\chi }}_{ef}\left(G\right), is defined to be the smallest integer k such that G has a weakly edge-face k-coloring. In 2016, Fabrici conjectured that every connected, loopless, and bridgeless plane graph was weakly edge-face 5-colorable. In this paper, a sufficient condition is provided for the foregoing conjecture to prove that Halin graphs are weakly edge-face 5-colorable in which the upper bound 5 is the best possible.

Graphical abstract

Keywords

Halin graph / wheel graph / weakly edge-face coloring / weakly edge-face chromatic number

References

[1] BondyJ.A. , Murty, U.S.R., Graph Theory, London: Springer-Verlag, 2008

[2] Chen M., Raspaud, A. , Wang, W.F. . Plane graphs with maximum degree 6 are edge-face 8-colorable. Graphs Combin. 2014; 30: 861–874

[3] Chen M. , Wang, W.F. . The 2-dipath chromatic number of Halin graphs. Inform. Process. Lett. 2006; 99: 47–53

[4] Fabrici I., Jendrol, S. , Vrbjarová, M. . Facial entire colouring of plane graphs. Discrete Math. 2016; 339: 626–631

[5] Fiamčík . Simultaneous coloring of 4-valent maps. Math. Slovaca 1971; 21: 9–13

[6] Gong Q.Y. , Wu, J.L. . Edge-face coloring of Halin graphs. Inform. Tech. 2008; 7: 64–67

[7] Jucovič . On a problem in map coloring. Math. Slovaca 1969; 19: 225–227

[8] MelnikovL.S., Problem 9, In: Recent Advances in Graph Theory (Fiedler, M. ed.), Proceedings of the Second Czechoslovak Symposium, Prague, June, 1974, Academia Prague, Czechoslovak, 1975, p. 543

[9] Sanders D.P. , Zhao, Y. . On simultaneous edge-face colorings of plane graphs. Combinatorica 1997; 17: 441–445

[10] Sanders D.P. , Zhao, Y. . A five-color theorem. Discrete Math. 2000; 220: 279–281

[11] Sanders D.P. , Zhao, Y. . On improving the edge-face coloring theorem. Graphs Combin. 2001; 17: 329341

[12] Sereni J. , Stehlik, M. . Edge-face colouring of plane graphs with maximum degree nine. J. Graph Theory 2011; 66: 332–346

[13] Waller A.O. . Simultaneous colouring the edges and faces of plane graphs. J. Combin. Theory Ser. B 1997; 69: 219–221

[14] Wang W.F. , Lih, K. . A new proof of Melnikov’s conjecture on the edge-face coloring of plane graphs. Discrete Math. 2002; 253: 87–95

RIGHTS & PERMISSIONS

Higher Education Press 2025