The good-vertex conjecture for the independent-set bound
Statement
For a graph , let be its number of independent sets, let be the degree of , let be the number of isolated vertices, and define
A vertex is good for if
where is the set of neighbours of . Good-vertex conjecture. For every graph with at least one vertex, there is a vertex that is good for . This conjecture would imply Kahn's independent-set bound.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.