On the fractional chromatic number of monotone self-dual Boolean functions

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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2009-03, Vol.309 (4), p.867-877
Main Authors: Gaur, Daya Ram, Makino, Kazuhisa
Format: Article
Language:English
Subjects:
Algebra
Combinatorics
Combinatorics. Ordered structures
Convex and discrete geometry
Exact sciences and technology
Fractional chromatic number
Geometry
Graph theory
Hypergraph transversals
Mathematics
Monotone self-dual functions
Non-dominated coteries
Number theory
Order, lattices, ordered algebraic structures
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2008.01.028