A note on polynomials and f-factors of graphs
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)].
- Factorisation of greedoid polynomials of rooted digraphs
- A note on degree-constrained subgraphs
- scientific article; zbMATH DE number 7217234 (Why is no real title available?)
- Antifactors of regular bipartite graphs
- Combinatorial nullstellensatz modulo prime powers and the parity argument
- Factors of disconnected graphs and polynomials with nonnegative integer coefficients
- Modulo factors with bounded degrees
This page was built for publication: A note on polynomials and \(f\)-factors of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010679)
