Existence of difficult subgraph-counting identities
Existence of difficult subgraph-counting identities
Let be a graph with vertices. For a graph , write for the number of induced subgraphs of isomorphic to ; let and denote the subgraphs induced by the vertices not adjacent and adjacent to , respectively. A subgraph-counting identity has the form
Here are polynomials in , and the complexity condition is
for every .
Existence conjecture. For every , there is such an identity that holds for every graph with vertices, has one graph or with vertices, and is not in one of the easily described families.
The paper's proved identity supplies the first example outside the previously known easily described families. The conjecture proposes that difficult identities continue to exist at every complexity level .
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Alexander Engstrom, “A proof of the McKay-Radziszowski subgraph counting conjecture”, arXiv:1002.4304 (2010).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.