Graph-theory open problems

Louis Esperet

Author (arXiv only) · 55 problems

Title Source Status Imp. Posted
5-Flow Reconfiguration Connectivity arxiv open 2026-05-04
ℤₖ-connectivity implying ℤ_k-flow reconfiguration arxiv open 2026-05-04
Limit of c_r/r in regular digraphs arxiv open 2026-04-26
Directed tree-width linear constant in regular digraphs arxiv open 2026-04-26
Linear perimeter gap in vertex-transitive digraphs arxiv open 2026-02-18
Circumference equivalence vertex transitive digraphs arxiv open 2026-02-18
Longest cycles intersection in vertex transitive digraphs arxiv open 2026-02-18
Cycle lengths in vertex-transitive digraphs arxiv open 2026-02-18
Fractional chromatic number of K_r-free d-degenerate graphs arxiv open 2026-01-21
Sub-exponential vertex threshold for degenerate coloring arxiv open 2026-01-21
Coloring triangle-free degenerate graphs via LLL arxiv open 2026-01-21
Exponential order of K_r-free degenerate χ=d+1 graphs arxiv open 2026-01-21
Sub-linear χ_f for K_r-free degenerate graphs arxiv open 2026-01-21
Odd cycle orientations avoidable in digraphs arxiv open 2025-10-13
Height function characterizing non-avoidable digraphs arxiv open 2025-10-13
Avoidable orientations of C₄ arxiv open 2025-10-13
Characterization of Eulerian-avoidable digraphs arxiv open 2025-10-13
C₄ Eulerian-avoidability in orientations arxiv open 2025-10-13
NP-hardness of Circuit Distance for polytopes arxiv open 2025-10-02
6-regular critical graph without critical edge arxiv open 2025-08-12
Optimal χ-to-χᵈ ratio in K_{d+1} blowups arxiv open 2025-04-02
χ(G) bound via spectral radius for triangle-free graphs arxiv open 2024-12-31
Clustered chromatic number for odd-H-minor-free graphs arxiv open 2024-10-18
χ-ζ gap 3 for ω < 5 graphs arxiv open 2024-08-20
Convex drawings via pseudocircular characterization arxiv open 2024-07-27
Chromatic number of Kₜ-minor-free hypergraphs arxiv open 2024-04-19
3-colorability of K₃-minor-free hypergraphs arxiv open 2024-04-19
High chromatic number forcing high degeneracy out-neighbourhood arxiv open 2023-12-04
Cycle in out-neighbourhood for high-χ graphs arxiv open 2023-12-04
Scott–Seymour property for random tournaments arxiv open 2023-12-04
χ threshold for tournament out-neighbourhood 3-coloring arxiv open 2023-12-04
BST Rotation Distance Computational Complexity arxiv solved 2023-11-06
Flip Distance Complexity for Rectangulations arxiv open 2023-11-06
Fixed-k vertex-critical edge-robustness chromatic arxiv partial 2023-10-19
Induced Menger separation with bounded degree arxiv open 2023-09-14
H-minor-free choosability equal to v−1 arxiv open 2023-04-09
d(s) asymptotics in minimum-outdegree subdigraphs arxiv open 2022-10-23
3-flowability via K⁺₃,ₙ₋₃-free subcontraction arxiv open 2022-08-26
Actual diameter of arithmetic hyperbolic surfaces arxiv open 2022-07-26
Counting perfect matchings #P-hard for α=2 graphs arxiv solved 2022-07-13
Complexity of 2-F-PFC for star-pruned oriented trees arxiv open 2022-06-07
Infinite family of 4-vertex-critical arrangement graphs arxiv open 2022-05-17
7-choosability for K₄,₄- and K₃,₅-minor-free graphs arxiv open 2022-01-22
List chromatic number bound for K_{s,t}-minor-free graphs arxiv open 2022-01-22
List-choosability of K_{s,t}-minor-free graphs arxiv open 2022-01-22
Smallest K_{s,t}-minor Woodall counterexample arxiv partial 2022-01-22
k-planar partition bound tightness for convex sets arxiv open 2021-12-15
χ_ℓ ≤ 2t for K_t-minor-free graphs arxiv open 2021-10-18
Even directed circuit in oriented matroids arxiv open 2020-10-18
Pentagon contact representation algorithm termination arxiv open 2020-04-13
Circular F-colourability complexity dichotomy arxiv partial 2020-01-09
NP-completeness of circular F-coloring arxiv partial 2020-01-09
Complexity of fractional dichromatic number ≤ p arxiv open 2020-01-09
Directed Kneser graph existence for b-tuple colourings arxiv open 2020-01-09
Largest minor-closed class dichromatic number 2 arxiv open 2019-06-30