What is the largest possible pathwidth of an n-vertex cubic graph?
Open the “Subgraphs” section on Wikipedia →
Source: List of unsolved problems in mathematics (CC BY-SA 4.0)
All › Mathematics › Subgraphs
More in “Subgraphs”
- Barnette's conjecture
- Gilbert–Pollak conjecture on the Steiner ratio of the Euclidean plane that the Steiner ratio is \sqrt{3}/2
- Chvátal's toughness conjecture, that there is a number t such that every t-tough graph is Hamiltonian
- The cycle double cover conjecture
- The Erdős–Gyárfás conjecture on cycles with power-of-two lengths in cubic graphs
- The Erdős–Hajnal conjecture on large cliques or independent sets in graphs with a forbidden induced subgraph
- The Grünbaum–Nash-Williams conjecture on whether every 4-vertex-connected toroidal graph has a Hamiltonian cycle.
- The linear arboricity conjecture on decomposing graphs into disjoint unions of paths according to their maximum degree