Title of article :
On the fractional chromatic number of monotone self-dual Boolean functions
Author/Authors :
Gaur، نويسنده , , Daya Ram and Makino، نويسنده , , Kazuhisa، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Pages :
11
From page :
867
To page :
877
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.
Keywords :
Monotone self-dual functions , Non-dominated coteries , Hypergraph transversals , fractional chromatic number
Journal title :
Discrete Mathematics
Serial Year :
2009
Journal title :
Discrete Mathematics
Record number :
1598547
Link To Document :
بازگشت