Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A note on polynomials and f -factors of graphs. | A note on polynomials and f -factors of graphs Hamed Shirazi Dept of Combinatorics Optimization University of Waterloo Waterloo Ontario Canada mmirjala@ Jacques Verstraete Dept of Mathematics Statistics McGill University Montreal Quebec Canada jverstra@ Submitted May 12 2008 Accepted Jun 10 2008 Published Jun 20 2008 Mathematics Subject Classification 05C07 Abstract Let G V E be a graph and let f V 2Z be a function assigning to each v 2 V a set of integers in 0 1 2 . d v where d v denotes the degree of v in G. Lovasz 5 defines an f-factor of G to be a spanning subgraph H of G in which d 1 v 2 f v for all v 2 V. Using the combinatorial nullstellensatz of Alon 2 we prove that if If v d2d v e for all v 2 V then G has an f-factor. This result is best possible and verifies a conjecture of Addario-Berry Dalal Reed and Thomason 1 . 1 Introduction In this paper we are interested in the existence of f-factors of graphs where the term f-factor has a more general meaning than the traditional one. Let G V E be a graph and let f be a function assigning to each v 2 V a set f v of integers. Lovasz 5 defines an f-factor of G sometimes called a generalized f-factor 5 to be a subgraph of G in which d v 2 f v for all v 2 V. In the case If v I 1 Tutte s f-factor theorem gives a necesary and sufficient condition for the existence of an f-factor of G. No necessary and sufficient condition for an f-factor exists when we allow If v I 2 even when If v I 2 for all v 2 V since the decision problem of determining whether a graph has an f -factor is known to be algorithmically hard in this case. On the other hand Lovasz 5 showed that if no two consecutive integers in f v differ by more than two then there is a necessary and sufficient condition for an f-factor. We prove the following sufficient condition for f-factors which verifies a conjecture in Addario-Berry Dalal Reed and Thomason 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 N22 1 Theorem 1 Let G V E be
