The independent-set polynomial cover inequality for bipartite graphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.