A note on polynomials and \(f\)-factors of graphs
type: Item
instance of: scholarly article
title: A note on polynomials and \(f\)-factors of graphs
zbMATH Open document ID: 1160.05329
author: Hamed Shirazi
author: J. Verstraëte
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129822
full work available at URL: v15i1n22.html
review text: 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)].
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C78
zbMATH DE Number: 5540884
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540884