Geodesic
A note on polynomials and \(f\)-factors of graphs
The electronic journal of combinatorics, Tome 15 (2008)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/897
Classification : 05C70, 05C78 
@article{10_37236_897,
     author = {Hamed Shirazi and Jacques Verstra\"ete},
     title = {A note on polynomials and \(f\)-factors of graphs},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/897},
     zbl = {1160.05329},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/897/}
}
TY  - JOUR
AU  - Hamed Shirazi
AU  - Jacques Verstraëte
TI  - A note on polynomials and \(f\)-factors of graphs
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/897/
DO  - 10.37236/897
ID  - 10_37236_897
ER  - 
%0 Journal Article
%A Hamed Shirazi
%A Jacques Verstraëte
%T A note on polynomials and \(f\)-factors of graphs
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/897/
%R 10.37236/897
%F 10_37236_897
Hamed Shirazi; Jacques Verstraëte. A note on polynomials and \(f\)-factors of graphs. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/897

Cité par Sources :