A note on polynomials and \(f\)-factors of graphs (Q1010679): Difference between revisions

Summary: Let \(G = (V,E)\) be a graph, and let \(f : V \rightarrow 2^{\mathbb 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\). \textit{L. Lovász} [''Generalized factors of graphs,'' Combinat. Theory Appl., Colloquia Math. Soc. Janos Bolyai 4, 773--781 (1970; Zbl 0209.55301)] 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 \textit{L. Addario-Berry}, \textit{R.E.L. Aldred}, \textit{K. Dalal}, and \textit{B.A. Reed} [''Vertex colouring edge partitions,'' J. Comb. Theory, Ser. B 94, No.\,2, 237--244 (2005; Zbl 1074.05031)].