Compression with wildcards: All, or all maximum, anticlques of a graph
arXiv:0901.4417
Abstract
By definition an anticlique is an independent set of vertices of a graph . By duality all results obtained for anticliques carry over to cliques. (It is for technical reasons that we stick with anticliques throughout.) We display the set of all anticliques of in a compressed format that uses wildcards. Likewise (albeit less compressed) for the subfamily $MACL(G)\s Acl(G)$ of all maximum-cardinality members. The second task works particularly well for bipartite graphs (in fact for the broader class of König-Egarváry graphs). In this scenario Boolean functions (of type 2-CNF) will be important. Dilworth's lattice of all maximum antichains of a poset also features prominently.
45 pages