Graph-theory open problems

Tung Nguyen

Author (arXiv only) · 113 problems

Title Source Status Imp. Posted
Polynomial Nikiforov universality for graphs arxiv open 2026-04-18
√k bound for bipartite matching discrepancy arxiv open 2026-04-10
Constant bound on colour-balanced perfect matching imbalance arxiv open 2026-04-10
Colour-balanced error bounds for k≥3 spanning forests arxiv open 2026-04-10
Colour-balanced Hamilton cycle bounds in complete graphs arxiv open 2026-04-10
Anticoncentration bound for random spanning trees arxiv open 2026-03-18
Non-isomorphic spanning trees count lower bound arxiv open 2026-03-18
Superlinear monotone path cover for dense point sets arxiv open 2026-01-10
Crossing-free path cover lower bound cn arxiv open 2026-01-10
Minimum zig-zag path cover of complete geometric graphs arxiv open 2026-01-10
Schnyder wood limit of UIHPT arxiv open 2025-11-10
Schnyder woods existence on half-plane triangulations arxiv open 2025-11-10
Local limit of random wooded triangulations arxiv open 2025-11-10
Minimum transpositions in t-reachable networks arxiv open 2025-10-23
Minimum lazy transpositions in 2-uniformity networks arxiv open 2025-10-23
Quasi-isometry distortion improvement for subdivision-closed classes arxiv open 2025-10-02
Georgakopoulos–Papasoglu conjecture for trees and planar graphs arxiv open 2025-09-13
Coarse Menger conjecture for bounded genus arxiv solved 2025-09-10
Coarse Menger for surface-embedded graphs arxiv partial 2025-09-08
Isometric quasi-isometry in bounded tree-width arxiv partial 2025-09-05
Infinite family with no finite induced-saturated graphs arxiv open 2025-09-01
Disconnectedness of H-free graphs adjacency structure arxiv open 2025-09-01
Arc-reversal induced saturation in tournaments arxiv open 2025-09-01
Induced-saturated infinite tournament existence arxiv open 2025-09-01
Induced saturation for infinite k-uniform hypergraphs arxiv open 2025-09-01
Edge-colored induced saturation in infinite clique arxiv open 2025-09-01
Coarse Menger separation with distance 2 arxiv partial 2025-08-20
Second phase transition in r-neighbourhood shotgun assembly arxiv partial 2025-06-23
Sharp threshold for r-reconstructibility in G(n,p) arxiv open 2025-06-23
Signs model minimises Q₃ connectivity arxiv open 2025-06-23
Giant component threshold in hypercube percolation arxiv open 2025-06-23
Superexponential growth of R₂(2,n) arxiv open 2024-12-31
log R₂(2,n) polynomial in log M₂(n) arxiv open 2024-12-31
Strong 2-kernel size bound in split digraphs arxiv open 2024-09-08
Optimal size of (1,r)-cover-free families arxiv open 2024-04-04
Optimal randomised non-adaptive MIS reconstruction arxiv open 2024-04-04
Adaptive gap for Δ-degree graph reconstruction arxiv open 2024-04-04
H-coloring graph polynomial determination arxiv open 2024-02-29
Finite H-family distinguishing random graphs arxiv open 2024-02-29
Pure pair in triangle-free 3-blockade arxiv open 2024-02-06
Polynomial pure pairs for ordered graphs H arxiv open 2024-02-06
Strong transversal property forest characterization arxiv open 2024-02-06
Prescribed Ramsey growth rate approximation arxiv open 2023-11-03
Polynomial degree-bounding for hereditary degree-bounded classes arxiv solved 2023-11-01
Polynomial bound for C₄-free average degree arxiv open 2023-11-01
Linear pure pair in sparse H-free graphs arxiv open 2023-10-29
Stronger coherence condition for pure pairs arxiv open 2023-10-29
Girth-preserving χ-boundedness for triangle-free F arxiv open 2023-09-18
Boundary rigidity of k-dimensional cube complexes arxiv partial 2023-09-08
Strong EH-property via backedge forest tournaments arxiv open 2023-08-08
D₅-free condition necessity in strong EH-property arxiv open 2023-08-08
Flash-rainbow tournament edge-coloring formula arxiv open 2023-06-01
Polynomial χ-boundedness for H-free forest classes arxiv partial 2023-03-22
Nondominating broom copy in χ-bounded graphs arxiv open 2023-03-22
Forests are multibounding chromatic bound arxiv open 2023-03-21
Polynomial χ-bound for path-induced rooted tree arxiv open 2023-02-17
Polynomial χ-bounding in Gyárfás-Sumner arxiv partial 2023-02-17
Threshold (1+ε)/n for Ω(n) distance reconstruction arxiv solved 2023-01-26
Polynomial χ-boundedness for forest-free graphs arxiv partial 2023-01-10
Polynomial χ-bound via τ_d for path-free graphs arxiv partial 2023-01-10
Polynomial τ_d-boundedness implies polynomial bound arxiv open 2023-01-10
Polynomial χ-boundedness for forest-free graphs arxiv partial 2022-10-02
Exact formula for U_t(n) lazy transpositions arxiv partial 2022-08-13
ε-restricted union cover for H-free graphs arxiv open 2022-08-03
K₆ minor in 6-regular graphs arxiv open 2022-04-21
δ≥6, Δ≤8 forces K_6 minor arxiv open 2022-04-21
K₆ minor from minimum degree five in bipartite graphs arxiv open 2022-04-21
K₅ minor via degree bounds in bipartite graphs arxiv open 2022-04-21
Characterisation of poly-χ-bounded hereditary classes arxiv open 2022-02-18
Polynomial χ-boundedness for odd-cycle k-multihole graphs arxiv open 2022-02-18
Polynomial χ-boundedness for H-free forests arxiv partial 2022-02-18
Closure of good trees under disjoint union arxiv partial 2022-02-18
All graphs self-isolating arxiv open 2022-02-18
Dictator-to-XOR Lipschitz inverse gap arxiv open 2021-12-10
Clique algorithm optimality in active clustering arxiv open 2021-10-27
Known forests for Esperet's polynomial χ-boundedness arxiv disproved 2021-07-25
Pervasiveness of forests of lanterns arxiv open 2021-05-21
Exact exponent constant for tournament path powers arxiv open 2021-02-16
Erdős–Hajnal property for {C₈, C̄₈} arxiv open 2021-02-09
n/polylog(n) bound for ordered pure pairs arxiv open 2021-01-10
Linear anticomplete pairs in sparse H-free graphs arxiv partial 2020-12-07
K₃ polynomial anticomplete pair property arxiv open 2020-12-07
Sparse pairs in H-free ε-bounded graphs arxiv partial 2020-12-07
Tight bound characterisation of φ(x,y) arxiv open 2020-12-07
Symmetry of biconstrained ψ function arxiv open 2020-12-07
Poly-time excess-3 induced st-path detection arxiv open 2020-09-06
Heavy path extension for long odd holes arxiv open 2020-09-06
Fixed-ℓ long odd hole detection complexity arxiv open 2020-09-06
Extremal self-annihilating subspaces in exterior algebra arxiv open 2020-07-14
Extremal mutually annihilating pairs in exterior algebra arxiv open 2020-07-14
Forest-filleting of coherent ideals arxiv open 2020-06-02
n^{5/2} threshold for 3-graph homeomorphs arxiv partial 2020-04-06
Moderate deviation rates in sparse G(n,m) arxiv partial 2020-02-10
Widespread multigraph conjecture arxiv open 2019-08-27
χ₂-boundedness via J-subdivision-free graphs arxiv open 2019-08-27
χ-boundedness for H-subdivision-free graphs arxiv open 2019-08-27
1-ball reconstruction threshold gap in Qₙ arxiv open 2019-07-16
3-colourability complexity of P_t-free graphs arxiv partial 2019-03-22
Polynomial-time MIS on Pₜ-free graphs arxiv partial 2019-03-22
NP-completeness of vertex-disjoint paths, stability two arxiv open 2018-12-23
Consecutive hole lengths for bounded clique number arxiv open 2018-12-04
3-colourability of ternary graphs arxiv open 2018-09-28
Clustered chromatic number via treedepth bound arxiv partial 2018-07-29
Polynomial δ Dependence in Rödl's Theorem arxiv partial 2018-03-09
Consecutive holes in bounded clique number graphs arxiv open 2018-02-12
Bounded-gap sets are constricting arxiv open 2018-02-12
Constricting set with density zero arxiv open 2018-02-12
4-hole in controlled triangle-free graphs arxiv open 2018-02-12
Chromatic concentration lower bound in G(n,p) arxiv solved 2017-10-18
Projective plane structure in near-extremal r-partite hypergraphs arxiv open 2017-10-06
s Consecutive Rainbow Vertices in Holes arxiv open 2017-07-03
Uniquely-covered induced path in triangle-free graphs arxiv open 2017-07-03
Block tree diameter gap beyond √(log n) arxiv solved 2016-05-16