Abstract
A plane graph G is k-edge-face colorable if the elements of \(E(G)\cup F(G)\) can be colored with k colors such that any two adjacent or incident elements receive different colors. G is edge-face L-list colorable if for a given list assignment \(L=\{L(x){\mid }x\in E(G)\cup F(G)\}\), there exists a proper edge-face coloring \(\pi \) of G such that \(\pi (x)\in L(x)\) for all \(x\in E(G)\,\cup \,F(G)\). If G is edge-face L-list colorable for any list assignment with \(|L(x)|=k\) for all \(x\in E(G)\,\cup \,F(G)\), then G is edge-face k-choosable. The edge-face list chromatic number is defined to be the smallest integer k such that G admits an edge-face k-list coloring.
In this paper, we first use the famous Combinatorial Nullstellensatz to characterize the edge-face list chromatic number of wheel graphs by using Matlab. Then we show that every Halin graph G with \(\varDelta (G)\ge 6\) is edge-face \(\varDelta (G)\)-choosable and this bound is sharp. Our proof demonstrates how edge-face choosability problems can numerically be approached by the use of computer algebra systems and the Combinatorial Nullstellensatz.
M. Chen—Supported by ZJNSFC (No. LY19A010015), NSFC (Nos. 11971437 and 11701136) and NSFHB (No. A2020402006).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alon, N.: Combinatorial Nullstellensatz. Comb. Probab. Comput. 8, 7–29 (1999)
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. MacMillan, New York (1976)
Chen, M., Raspaud, A., Wang, W.F.: Plane graphs with maximum degree \(6\) are edge-face \(8\)-colorable. Graphs Comb. 30, 861–874 (2014)
Fiamčík, J.: Simultaneous colouring of 4-valent maps. Mat. Časopis Sloven. Akad. Vied 21, 9–13 (1971)
Gong, Q.Y., Wu, J.L.: Edge-face coloring of Halin graphs. Inform. Tech. 7, 64–67 (2008)
Jucovič, E.: On a problem in map colouring. Mat. Časopis Sloven. Akad. Vied 19, 225–227 (1969)
Kaul, H., Mudrock, J.A.: Combinatorial Nullstellensatz and DP-coloring of graphs. arXiv:2003.01112v1 (2020)
Mel’nikov, L.S.: Problem 9. In: Fiedler, M. (ed.) Proceedings of the Second Czechoslovak Symposium on Recent Advances in Graph Theory, Prague, June 1974, pp. 543. Academia Prague, Czechoslovak (1975)
Sander, D.P., Zhao, Y.: On simultaneous edge-face colorings of plane graphs. Combinatorica 17, 441–445 (1997)
Sander, D.P., Zhao, Y.: A five-color theorem. Discrete Math. 220, 279–281 (2000)
Sander, D.P., Zhao, Y.: On improving the edge-face coloring theorem. Graphs Comb. 17, 329–341 (2001)
Waller, A.O.: Simultaneously colouring the edges and faces of plane graphs. J. Comb. Theory Ser. B 69, 219–221 (1997)
Wang, W.F., Lih, K.: A new proof of Melnikov’s conjecture on the edge-face coloring of plane graphs. Discrete Math. 253, 87–95 (2002)
Wang, W.F., Lih, K.: The edge-face choosability of plane graphs. European J. Comb. 25, 935–948 (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendix
Appendix
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Jin, X., Chen, M., Pang, X., Huo, J. (2020). Edge-Face List Coloring of Halin Graphs. In: Zhang, Z., Li, W., Du, DZ. (eds) Algorithmic Aspects in Information and Management. AAIM 2020. Lecture Notes in Computer Science(), vol 12290. Springer, Cham. https://doi.org/10.1007/978-3-030-57602-8_43
Download citation
DOI: https://doi.org/10.1007/978-3-030-57602-8_43
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-57601-1
Online ISBN: 978-3-030-57602-8
eBook Packages: Computer ScienceComputer Science (R0)