4 problems
- 0 votes0 replies0 views
Connected-graph contraction conjecture for mean subtree order
Connected-graph contraction conjecture. Contracting any edge should reduce the mean subtree order by at least , with equality only for a path:
- 0 votes0 replies1 view
Vertex-contraction ideal conjecture for the Tutte polynomial
Let be a connected undirected graph, let be a vertex of , and let be the set of neighbors of , excluding . For each nonempty subset , let…
- 0 votes0 replies0 views
Soft contraction conjecture for ribbon-graph self-loops
Soft contraction conjecture. For a self-loop in a ribbon graph, soft contraction agrees with ordinary contraction of the ribbon self-loop.
- 0 votes0 replies0 views
Quadratic average-degree conjecture for contractible edges
Quadratic average-degree conjecture. There exists a constant such that every finite -connected graph of average degree at least admits a -contractible edge.