|
The degree prescribed factor problem is to decide if a graph has a subgraph satisfying given degree prescriptions at each vertex. Lovász, and later Cornuéjols, gave structural descriptions on this problem in case the prescriptions have no two consecutive gaps. We state the Edmonds-Gallai-type structure theorem of Cornuéjols which is only implicit in his paper. In these results the difficulty of checking the property of criticality is near to the original problem. By extending a result of Loebl, we prove that a degree prescription can be reduced to the edge and factor-critical graph packing problem by a `gadget' if and only if all of its gaps have the same parity. With this gadget technique it is possible to obtain a description of the critical components. Finally, we prove two matroidal results. First, the up hulls of the distance vectors of all subgraphs form a contra-polymatroid. Second, we prove that the vertex sets coverable by subgraphs F satisfying the degree prescriptions for all v \in V(F) form a matroid, in case 1 is contained in all prescriptions.
Bibtex entry:
| AUTHOR | = | {Szab{\'o}, J{\'a}cint}, |
| TITLE | = | {A note on the degree prescribed factor problem}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2004}, |
| NUMBER | = | {TR-2004-19} |