The independent-set polynomial cover inequality for bipartite graphs
Let be a finite bipartite graph, let be its -cover, and let be its multivariate independent-set polynomial. Extend the natural projection from to to a ring homomorphism by mapping each indeterminate to . For polynomials with nonnegative coefficients, write when every monomial coefficient of is at most the corresponding coefficient of . Independent-set polynomial cover inequality. For any bipartite graph and its -cover , one has
The inequality compares the projected independent sets of a cover with the independent sets in disjoint copies of the base graph. It was checked computationally for many examples, but no resolution is supplied here.
References
Primary source
Yusuke Watanabe, “A conjecture on independent sets and graph covers”, arXiv:1109.2445 (2011).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.