论文标题
关于两部分图中有规定残基的大型诱导子图的注释
A note on large induced subgraphs with prescribed residues in bipartite graphs
论文作者
论文摘要
斯科特证明了每一个$ k \ ge2 $，存在一个常数$ c（k）> 0 $，以至于每两部分$ n $ n $ vertex $ g $没有孤立的顶点，都存在诱发的$ h $ of $ h $ $ c（k）n $的$ h $ for至少$ \ textrm {$ \ textrm {deg} $ {d $ {v）。 \ in H $。斯科特（Scott）猜想$ c（k）=ω（1/k）$，这将紧密到乘法常数。我们确认这个猜想。
It was proved by Scott that for every $k\ge2$, there exists a constant $c(k)>0$ such that for every bipartite $n$-vertex graph $G$ without isolated vertices, there exists an induced subgraph $H$ of order at least $c(k)n$ such that $\textrm{deg}_H(v) \equiv 1\pmod{k}$ for each $v \in H$. Scott conjectured that $c(k) = Ω(1/k)$, which would be tight up to the multiplicative constant. We confirm this conjecture.
