含有3-圈的平面图的有效染色数
The Valid Coloring Number of Plane Graphs Containing3-Cycles
DOI: 10.12677/AAM.2025.141005, PDF,   
作者: 沈儒雄：浙江师范大学数学科学学院，浙江 金华
关键词: 平面图；彩虹面；有效染色；Plane Graph； Rainbow Face； Valid Coloring
摘要: 给定平面图G的一个顶点染色，如果图G的某个面F 的所有顶点颜色各不相同，我们称面F 为彩 虹面。 而如果平面图G中没有任何一个面是彩虹面，我们称这种染色为有效染色. 在这种有效 染色方案中，所使用的颜色种类的最大值定义为该平面图的有效染色数，记作χf (G)。 Jungiˇc, Kr´al／和Sˇkrekovski研究了一类围长至少为4的平面图的有效染色数。 本文主要研究了一类既包 含3-圈又包含长度至少为5的面圈的平面图的有效染色数井得到了它的下界。
Abstract: Given a vertex coloring of a plane graph G, if all the vertices of a face F of G receive mutually different colors, then the face F is called a rainbow face. A valid coloring is a coloring of G such that no face of G is rainbow. The maximum number of colors used in a valid coloring of a plane graph G is referred to as the valid coloring number, denoted by χf (G). Jungiˇc, Kr´al／ and Sˇkrekovski focused on the valid coloring number of a class of plane graphs with girth at least 4. In this paper, we mainly study the valid coloring number of a class of plane graphs containing 3-cycles and faces with cycles of length at least 5 and get its lower bound.
文章引用：沈儒雄. 含有3-圈的平面图的有效染色数[J]. 应用数学进展, 2025, 14(1): 24-32. https://doi.org/10.12677/AAM.2025.141005

参考文献

[1] Czap, J. and Jendrol’, S. (2017) Facially-constrained Colorings of Plane Graphs: A Survey. Discrete Mathematics, 340, 2691-2703.
https://doi.org/10.1016/j.disc.2016.07.026
[2] Zykov, A.A. (1974) Hypergraphs. Russian Mathematical Surveys, 29, 89-156.
https://doi.org/10.1070/rm1974v029n06abeh001303
[3] Ku¨ndgen, A. and Ramamurthi, R. (2002) Coloring Face-Hypergraphs of Graphs on Surfaces. Journal of Combinatorial Theory, Series B, 85, 307-337.
https://doi.org/10.1006/jctb.2001.2107
[4] Nakamoto, A., Negami, S., Ohba, K. and Suzuki, Y. (2016) Looseness and Independence Number of Triangulations on Closed Surfaces. Discussiones Mathematicae Graph Theory, 36, 545-554.
https://doi.org/10.7151/dmgt.1870
[5] Negami, S. (2005) Looseness Ranges of Triangulations on Closed Surfaces. Discrete Mathe- matics, 303, 167-174.
https://doi.org/10.1016/j.disc.2005.01.010
[6] Enami, K., Ozeki, K. and Yamaguchi, T. (2021) Proper Colorings of Plane Quadrangulations without Rainbow Faces. Graphs and Combinatorics, 37, 1873-1890.
https://doi.org/10.1007/s00373-021-02350-5
[7] Dvoˇr´ak, Z., Z., Jendrol’, S., Kral’, D. and Pap, G. (2009) Matchings and Nonrainbow Colorings. SIAM Journal on Discrete Mathematics, 23, 344-348.
https://doi.org/10.1137/060675927
[8] Jendrol’, S. (2006) Rainbowness of Cubic Plane Graphs. Discrete Mathematics, 306, 3321- 3326.
https://doi.org/10.1016/j.disc.2006.06.012
[9] Jendrol’, S. and Schro¨tter, Sˇ. (2008) On Rainbowness of Semiregular Polyhedra. Czechoslovak Mathematical Journal, 58, 359-380.
https://doi.org/10.1007/s10587-008-0021-z
[10] Alon, N. (1983) On a Conjecture of Erdo˝s, Simonovits, and S´os Concerning AntiTheorems. Journal of Graph Theory, 7, 91-94.
https://doi.org/10.1002/jgt.3190070112
[11] Axenovich, M. and Ku¨ndgen, A. (2001) On a Generalized Anti-Ramsey Problem. Combina- torica, 21, 335-349.
https://doi.org/10.1007/s004930100000
[12] Burr, S.A., Erdo˝s, P., Graham, R.L. and T. S´os, V. (1989) Maximal Antiramsey Graphs and the Strong Chromatic Number. Journal of Graph Theory, 13, 263-282.
https://doi.org/10.1002/jgt.3190130302
[13] Erdo˝s, P., Simonovits, M. and Sos, V.T. (1975) Anti-Ramsey Theorems. In: Hajnal, A., Rado, R. and S´os, V.T., Eds., Infinite and Finite Sets: To Paul Erd˝os on His 60th Birthday, North- Holland, 633-643.
[14] Jiang, T. (2002) Edge-Colorings with No Large Polychromatic Stars. Graphs and Combina- torics, 18, 303-308.
https://doi.org/10.1007/s003730200022
[15] Jiang, T. and West, D. (2003) On the Erdo˝s-Simonovits-So´s Conjecture about the Anti-Ramsey Number of a Cycle. Combinatorics, Probability and Computing, 12, 585-598.
https://doi.org/10.1017/s096354830300590x
[16] Jiang, T. and West, D.B. (2004) Edge-Colorings of Complete Graphs That Avoid Polychro- matic Trees. Discrete Mathematics, 274, 137-145.
https://doi.org/10.1016/j.disc.2003.09.002
[17] Simonovits, M. and S´os, V.T. (1984) On Restricted Colourings of Kn. Combinatorica, 4, 101- 110.
https://doi.org/10.1007/bf02579162
[18] Diwan, A.A. (2002) Disconnected 2-Factors in Planar Cubic Bridgeless Graphs. Journal of Combinatorial Theory, Series B, 84, 249-259.
https://doi.org/10.1006/jctb.2001.2079
[19] Dvoˇr´ak, Z. and Kra´l’, D. (2001) On Planar Mixed Hypergraphs. The Electronic Journal of Combinatorics, 8, R35.
https://doi.org/10.37236/1579
[20] Kobler, D. and Ku¨ndgen, A. (2001) Gaps in the Chromatic Spectrum of Face-Constrained Plane Graphs. The Electronic Journal of Combinatorics, 8, N3.
https://doi.org/10.37236/1588
[21] Ku¨ndgen, A., Mendelsohn, E. and Voloshin, V. (2000) Colouring Planar Mixed Hypergraphs. The Electronic Journal of Combinatorics, 7, R60.
https://doi.org/10.37236/1538
[22] Penaud, J.G. (1975) Une Propri´et´e De Bicoloration Des Hypergraphes Planaires. Cahiers Cen- tre Etudes Recherche Op´er, 17, 345-349.
[23] Ramamurthi, R. and West, D.B. (2004) Maximum Face-Constrained Coloring of Plane Graphs. Discrete Mathematics, 274, 233-240.
https://doi.org/10.1016/j.disc.2003.09.001
[24] Thomassen, C. (1994) Gro¨tzsch’s 3-Color Theorem and Its Counterparts for the Torus and the Projective Plane. Journal of Combinatorial Theory, Series B, 62, 268-279.
https://doi.org/10.1006/jctb.1994.1069
[25] Kra´l’, D. (2004) On Maximum Face-Constrained Coloring of Plane Graphs with No Short Face Cycles. Discrete Mathematics, 277, 301-307.
https://doi.org/10.1016/j.disc.2003.08.001
[26] Jungi´c, V., Kra´l’, D. and Sˇkrekovski, R. (2006) Colorings of Plane Graphs with No Rainbow Faces. Combinatorica, 26, 169-182.
https://doi.org/10.1007/s00493-006-0012-3
[27] Dvoˇr´ak, Z., Kra´l／, D. and Sˇkrekovski, R. (2009) NonColorings of 34and 5Plane Graphs. Journal of Graph Theory, 63, 129-145.
https://doi.org/10.1002/jgt.20414
[28] West, D.B. (2011) A Short Proof of the Berge-Tutte Formula and the Gallai-Edmonds Struc- ture Theorem. European Journal of Combinatorics, 32, 674-676.
https://doi.org/10.1016/j.ejc.2011.01.009

为你推荐