most recent 30 from http://mathoverflow.net 2013-06-19T19:28:53Z http://mathoverflow.net/feeds/question/93061 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/93061/degree-conditions-for-k-factor Felix Goldberg 2012-04-04T02:16:27Z 2012-04-04T17:53:36Z

<p>I am looking for a simple degree conditon that ensures the existence of a k-factor in a graph. The k is supposed to be relatively high and I don't mind the condition being a bit strict. Ideally, something of the form $\delta(G) \geq f(k)$. Any suggestions? 10x!</p> <p>To clarify a bit what I'm after: there is a theorem by Nishimura that ensures a k-factor for k not larger than n/4 or so. But I want a k-factor with k approaching n. </p> <p><a href="http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190160205/abstract" rel="nofollow">http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190160205/abstract</a></p>

http://mathoverflow.net/questions/93061/degree-conditions-for-k-factor/93092#93092 Gjergji Zaimi 2012-04-04T10:04:20Z 2012-04-04T17:53:36Z

<p>A similar theorem is proved in <a href="http://www.math.unl.edu/~shartke2/math/papers/min-deg-k-factor.pdf" rel="nofollow">"Relating minimum degree and the existence of a k-factor"</a> by Hartke, Martin and Seacrest. </p> <p>They show that a graph $G$ on $n$ vertices with minimum degree $\delta\geq \frac{n}{2}$ contains a $k$-factor if $kn$ is even and $$k&lt; \frac{\delta+\sqrt{2\delta n-n^2+8}}{2}.$$</p> <p>Moreover they show that this is optimal up to a small additive constant ($\le 1$). Notice that as $\delta\to n$ we have $k\to n$, as well.</p>