|
|
含有3-圈的平面图的有效染色数
|
Abstract:
给定平面图G的一个顶点染色，如果图G的某个面F 的所有顶点颜色各不相同，我们称面F 为彩 虹面。 而如果平面图G中没有任何一个面是彩虹面，我们称这种染色为有效染色. 在这种有效 染色方案中，所使用的颜色种类的最大值定义为该平面图的有效染色数，记作χf (G)。 Jungiˇc, Kr′al／和Sˇkrekovski研究了一类围长至少为4的平面图的有效染色数。 本文主要研究了一类既包 含3-圈又包含长度至少为5的面圈的平面图的有效染色数井得到了它的下界。
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.
| [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 |
