A Note on Polynomials and $f$-Factors of Graphs

  • Hamed Shirazi
  • Jacques Verstraëte

Abstract

Let $G = (V,E)$ be a graph, and let $f : V \rightarrow 2^{\Bbb Z}$ be a function assigning to each $v \in V$ a set of integers in $\{0,1,2,\dots,d(v)\}$, where $d(v)$ denotes the degree of $v$ in $G$. Lovász defines an $f$-factor of $G$ to be a spanning subgraph $H$ of $G$ in which $d_{H}(v) \in f(v)$ for all $v \in V$. Using the combinatorial nullstellensatz of Alon, we prove that if $|f(v)| > \lceil {1\over 2}d(v) \rceil$ for all $v \in V$, then $G$ has an $f$-factor. This result is best possible and verifies a conjecture of Addario-Berry, Dalal, Reed and Thomason.

Published
2008-06-20
Article Number
N22