首页 | 本学科首页   官方微博 | 高级检索  
     


The size Ramsey number of short subdivisions of bounded degree graphs
Authors:Yoshiharu Kohayakawa,Troy Retter,Vojt   ch R  dl
Affiliation:Yoshiharu Kohayakawa,Troy Retter,Vojtěch Rödl
Abstract:For graphs G and F, write urn:x-wiley:10429832:media:rsa20783:rsa20783-math-0001 if any coloring of the edges of G with urn:x-wiley:10429832:media:rsa20783:rsa20783-math-0002 colors yields a monochromatic copy of the graph F. Suppose urn:x-wiley:10429832:media:rsa20783:rsa20783-math-0003 is obtained from a graph S with s vertices and maximum degree d by subdividing its edges h times (that is, by replacing the edges of S by paths of length h + 1). We prove that there exists a graph G with no more than urn:x-wiley:10429832:media:rsa20783:rsa20783-math-0004 edges for which urn:x-wiley:10429832:media:rsa20783:rsa20783-math-0005 holds, provided that urn:x-wiley:10429832:media:rsa20783:rsa20783-math-0006. We also extend this result to the case in which Q is a graph with maximum degree d on q vertices with the property that every pair of vertices of degree greater than 2 are distance at least h + 1 apart. This complements work of Pak regarding the size Ramsey number of “long subdivisions” of bounded degree graphs.
Keywords:probabilistic methods  random graphs  regularity method  Size‐Ramsey numbers  subdivisions of graphs
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号