Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650156 | Discrete Mathematics | 2009 | 11 Pages |
Abstract
We compute the exact fractional chromatic number for several classes of monotone self-dual Boolean functions. We characterize monotone self-dual Boolean functions in terms of the optimal value of an LP relaxation of a suitable strengthening of the standard IP formulation for the chromatic number. We also show that determining the self-duality of a monotone Boolean function is equivalent to determining the feasibility of a certain point in a polytope defined implicitly.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Daya Ram Gaur, Kazuhisa Makino,