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


Bounded diameter arboricity
Authors:Martin Merker  Luke Postle
Institution:1. Department of Applied Mathematics and Computer Science, Technical University of Denmark, Denmark;2. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada
Abstract:We introduce the notion of bounded diameter arboricity. Specifically, the diameter-urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0001 arboricity of a graph is the minimum number urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0002 such that the edges of the graph can be partitioned into urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0003 forests each of whose components has diameter at most urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0004. A class of graphs has bounded diameter arboricity urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0005 if there exists a natural number urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0006 such that every graph in the class has diameter-urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0007 arboricity at most urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0008. We conjecture that the class of graphs with arboricity at most urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0009 has bounded diameter arboricity at most urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0010. We prove this conjecture for urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0011 by proving the stronger assertion that the union of a forest and a star forest can be partitioned into two forests of diameter at most 18. We use these results to characterize the bounded diameter arboricity for planar graphs of girth at least urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0012 for all urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0013. As an application we show that every 6-edge-connected planar (multi)graph contains two edge-disjoint urn:x-wiley:03649024:media:jgt22416:jgt22416-math-0014-thin spanning trees. Moreover, we answer a question by Mütze and Peter, leading to an improved lower bound on the density of globally sparse Ramsey graphs.
Keywords:arboricity  bounded diameter  Ramsey density  thin spanning trees
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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