Integer decomposition property
A polyhedron P has the integer decomposition property, if for any natural number k and any integer vector [math]x\in kP[/math], there exist k integer vectors [math]x_1,\ldots,x_k\in P[/math] with [math]x_1+\ldots+x_k=x[/math]. Here kP is the set of vectors which can be decomposed to the sum of k (not necessarly integer) vectors in P. Polytopes having the integer decomposition property are also called normal polytopes.
Some classes of polyhedra with integer decomposition property:
- intersection of two base orderable matroids,
- polyhedron of arborescences (see Edmonds' disjoint arborescences theorem),
- polyhedra defined by nearly TU matrices (Gijswijt ),
- projections of polyhedra defined by TU matrices (Sebő ),
- certain polyhedra defined by k-balanced matrices (Zambelli ),
- stable set polytope of claw-free t-perfect graphs and h-perfect line-graphs (Benchetrit ).
- D. Gijswijt, Integer decomposition for polyhedra defined by nearly totally Unimodular matrices, DOI link
- A. Sebő, Path Partitions, Cycle Covers and Integer Decomposition, DOI link, author link
- G. Zambelli, Colorings of k-balanced matrices and integer decomposition property of related polyhedra, DOI link, Author link
- Y. Benchetrit, Integer round-up property for the chromatic number of some h-perfect graphs, arXiv link