8 problems

0 votes0 replies0 views
The correspondence coloring conjecture for $K_5$ -minor-free graphs
Correspondence coloring conjecture. The graph $G$ has $6$ disjoint $\mathbf{M}$ -colorings. Equivalently,
Conjectureopencorrespondence-coloring graph-coloring minor-free-graphsarXiv posted 2 days ago
0 votes0 replies0 views
Chen–Zhang's signless Laplacian extremal conjecture for $K_{s,t}$ -minor-free graphs
Chen–Zhang's conjecture.
Conjectureopenminor-free-graphs signless-laplacian spectral-graph-theoryarXiv posted 2 days ago
0 votes0 replies0 views
Class 1 conjecture for $K_5$ -minor free graphs of maximum degree six
Edge-coloring conjecture. Then $G$ is class $1$ .
Conjectureopenedge-coloring graph-coloring minor-free-graphsarXiv posted 2 days ago
0 votes0 replies0 views
Linear maximum degree conjecture for minor-free path-pairable graphs
Linear maximum degree conjecture. For any $t$ there exists a constant $c=c(t)$ such that every path-pairable graph on $n$ vertices without a $K_t$ minor must contain a vertex of de…
Conjectureopengraph-theory minor-free-graphs path-pairable-graphsarXiv posted 2 days ago
0 votes0 replies2 views
Ogorodnikov–Oum–Wood's defective chromatic number conjecture for minor-free graphs
Ogorodnikov–Oum–Wood's conjecture. For every connected graph $H$ ,
Conjectureopengraph-colourings minor-free-graphs tree-deptharXiv posted 2 days ago
0 votes0 replies0 views
Integer flow-cut gap conjecture for minor-free graphs
For a graph, compare the maximum integer concurrent flow with the sparsest cut; the flow-cut gap is the ratio between these quantities. The integer flow-cut gap conjecture. In mino…
Conjectureopenflow-cut-gaps graph-algorithms minor-free-graphsarXiv posted 2 days ago
0 votes0 replies0 views
Constant-congestion integrality-gap conjecture for maximum edge-disjoint paths in minor-closed families
Let ${\cal G}$ be any proper minor-closed family of graphs. The constant-congestion integrality-gap conjecture. The integrality gap of the flow LP for maximum edge-disjoint paths i…
Conjectureopengraph-algorithms integrality-gaps minor-free-graphsarXiv posted 2 days ago
0 votes0 replies0 views
The square-root query-complexity conjecture for testing H-minor freeness
Square-root query-complexity conjecture. For every $H$ , being $H$ -minor free can be tested with one-sided error using $\tilde{O}(\sqrt{n})$ queries, where $n$ is the number of vert…
Conjectureopenbounded-degree-graphs minor-free-graphs property-testingarXiv posted 2 days ago