×

Planar Ramsey graphs. (English) Zbl 1422.05066

Summary: We say that a graph \(H\) is planar unavoidable if there is a planar graph \(G\) such that any red/blue coloring of the edges of \(G\) contains a monochromatic copy of \(H\), otherwise we say that \(H\) is planar avoidable. That is, \(H\) is planar unavoidable if there is a Ramsey graph for \(H\) that is planar. It follows from the four-color theorem and a result of D. Gonçalves [in: Proceedings of the 37th annual ACM symposium on theory of computing, STOC’05. Baltimore, MD, USA, May 22–24, 2005. New York, NY: Association for Computing Machinery (ACM). 504–512 (2005; Zbl 1192.05113)] that if a graph is planar unavoidable then it is bipartite and outerplanar. We prove that the cycle on 4 vertices and any path are planar unavoidable. In addition, we prove that all trees of radius at most 2 are planar unavoidable and there are trees of radius 3 that are planar avoidable. We also address the planar unavoidable notion in more than two colors.

MSC:

05C55 Generalized Ramsey theory
05C10 Planar graphs; geometric and topological aspects of graph theory
05D10 Ramsey theory

Citations:

Zbl 1192.05113

References:

[1] I. Algor and N. Alon. The star arboricity of graphs. Discrete Mathematics, 75:11-22, 1989. · Zbl 0684.05033
[2] K. Appel and W. Haken. Every planar map is four colorable. Illinois Journal of Mathematics, 21:429-490, 1977. · Zbl 0387.05009
[3] H. Broersma, F. Fomin, J. Kratochv´ıl, and G. Woeginger. Planar graph coloring avoiding monochromatic subgraphs: trees and paths make it difficult. Algorithmica, 44:343-361, 2006. · Zbl 1095.68075
[4] L. J. Cowen, R. H. Cowen, and D. R. Woodall. Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. Journal of Graph Theory, 10.2:187-195, 1986. · Zbl 0596.05024
[5] S. Hakimi. On the degrees of the vertices of a directed graph. Journal of Franklin Institute, 279:290-308, 1965. · Zbl 0173.26404
[6] S. Hakimi, J. Mitchem, and E. Schmeichel. Star arboricity of graphs. Discrete Mathematics, 149:93-98, 1996. · Zbl 0843.05037
[7] D. Gale. The game of Hex and the Brouwer fixed-point theorem. American Mathematical Monthly, 86:818-827, 1979. · Zbl 0448.90097
[8] D. Gon¸calves. Edge partition of planar graphs into two outerplanar graphs. In STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 504-512. 2005. · Zbl 1192.05113
[9] D. Gon¸calves.Caterpillar arboricity of planar graphs.Discrete Mathematics, 307:2112-2121, 2007. · Zbl 1121.05038
[10] I. Gorgol. Planar Ramsey numbers. Discussiones Mathematicae Graph Theory, 25(12):45-50, 2005. · Zbl 1077.05063
[11] M. Merker and L. Postle. Bounded diameter arboricity. Journal of Graph Theory, 1-13, 2018. · Zbl 1429.05054
[12] C. S. J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs. Journal of London Mathematical Society, 36:445-450, 1961. · Zbl 0102.38805
[13] J. Neˇsetˇril and V. R¨odl. The Ramsey properties of graphs with forbidden complete subgraphs. Journal of Combinatorial Theory, Series B, 20:243-249, 1976. · Zbl 0329.05115
[14] J. Neˇsetˇril and V. R¨odl. On Ramsey graphs without short cycles of odd length. Commentationes Mathematicae Universitatis Carolinae, 20:565-582, 1979. · Zbl 0425.05025
[15] K. S. Poh. On the linear vertex arboricity of a planar graph. Journal of Graph Theory, 14.1:73-75, 1990. · Zbl 0705.05016
[16] F. Ramsey. On a problem in formal logic. Proceedings of London Mathematical Society, 30:264-286, 1927. · JFM 55.0032.04
[17] V. R¨odl and A. Ruci´nski. Lower bounds on probability thresholds for Ramsey properties. In Combinatorics, Paul Erd˝os is eighty, Vol. 1, Bolyai Soc. Math. Stud., pages 317-346. J´anos Bolyai Math. Soc., Budapest, 1993. the electronic journal of combinatorics 26(4) (2019), #P4.913 · Zbl 0790.05078
[18] R. Steinberg and C. A. Tovey. Planar Ramsey numbers, Journal of Combinatorial Theory, Series B, 59(2):288-296, 1993. · Zbl 0794.05091
[19] K. Walker. The Analogue of Ramsey Numbers for Planar Graphs. Bulletin of the London Mathematical Society, 1(2):187-190, 1969. · Zbl 0184.27705
[20] D. West. Introduction to graph theory Prentice Hall, Inc., Upper Saddle River, NJ, 1996. xvi+512 pp. the electronic journal of combinatorics 26(4) (2019), #P4.914 · Zbl 0845.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.