论文标题
在稀疏图的Holroyd-Talbot猜想上
On the Holroyd-Talbot Conjecture for Sparse Graphs
论文作者
论文摘要
给定图形$ g $，让$μ（g）$表示$ g $中最小的独立设置的大小。如果家庭中的每组中有某些元素，则一系列子集被称为星星。一个拆分顶点至少具有3个。Holroyd和Talbot猜想以下有关与图形中独立集合的家族相交的ERDőS-KO-RADO类型语句：如果$ 1 \ le r \ le r \ le \leμ（g）/2 $，则有一个相交的独立$ r $的家族的最大尺寸的家族，这是一颗星星。在本文中，我们在$ n $顶点上证明了稀疏图的类似语句：大致，对于$ r \ le o（n^{{1/3}）$的有界平均度图（n^{1/3}）$，用于有界图的图形，带有$ r \ le o（n^{1/2}）$，以及与$ r r r r r \ le o o o o（n^{1/2}）$（n^{1/3}）$（N^{1/3}）$（N^{1/3}）$（N^{1/3}）$（N^{1/3}）$（n^{1/2}）$（
Given a graph $G$, let $μ(G)$ denote the size of the smallest maximal independent set in $G$. A family of subsets is called a star if some element is in every set of the family. A split vertex has degree at least 3. Holroyd and Talbot conjectured the following Erdős-Ko-Rado type statement about intersecting families of independent sets in graphs: if $1\le r\le μ(G)/2$ then there is an intersecting family of independent $r$-sets of maximum size that is a star. In this paper we prove similar statements for sparse graphs on $n$ vertices: roughly, for graphs of bounded average degree with $r\le O(n^{1/3})$, for graphs of bounded degree with $r\le O(n^{1/2})$, and for trees having a bounded number of split vertices with $r\le O(n^{1/2})$.
