Graph-theory open problems

Tung Nguyen

Author (arXiv only) · 86 problems

Title Source Status Imp. Posted
Polynomial Nikiforov universality for graphs arxiv open 2026-04-18
Circular drawing characterization via forbidden type arxiv open 2026-01-19
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
Coarse Menger separation with distance 2 arxiv partial 2025-08-20
Planar crossing-free drawing in annulus arxiv open 2025-02-09
NP-characterization of weightable digraphs arxiv partial 2025-02-09
Strong 2-kernel size bound in split digraphs arxiv open 2024-09-08
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
Characterisation of ℓ-holed graphs ℓ ∈ {4,5,6} arxiv open 2023-12-21
Linear pure pair in sparse H-free graphs arxiv open 2023-10-29
Stronger coherence condition for pure pairs arxiv open 2023-10-29
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
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
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
ε-restricted union cover for H-free graphs arxiv open 2022-08-03
Dense minor edge density improvement arxiv partial 2022-06-01
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
Known forests for Esperet's polynomial χ-boundedness arxiv disproved 2021-07-25
Pervasiveness of forests of lanterns arxiv open 2021-05-21
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
Shortest even hole detection arxiv solved 2020-09-12
Polynomial detection of holes mod 3 arxiv open 2020-09-12
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
Forest-filleting of coherent ideals arxiv open 2020-06-02
Polynomial algorithm for fixed-k induced detours arxiv open 2020-05-26
Combinatorial MWIS algorithm for perfect graphs arxiv partial 2020-03-11
MWIS complexity in P₇-free graphs arxiv partial 2020-03-11
Outerplanar strongly perfect graph characterization arxiv open 2020-03-04
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
Bipartite Caccetta–Häggkvist short cycle arxiv partial 2019-07-24
Asymmetric out-degree girth bound for bipartite digraphs arxiv open 2019-07-24
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
Sparse Strong EH-property Characterizes Forests arxiv solved 2018-10-01
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
Maximum tight skew partitions in perfect graphs arxiv open 2017-07-12
s Consecutive Rainbow Vertices in Holes arxiv open 2017-07-03
Uniquely-covered induced path in triangle-free graphs arxiv open 2017-07-03
Majority 3-coloring of digraphs arxiv partial 2016-08-10
Majority 1/k out-neighbour colouring digraphs arxiv disproved 2016-08-10
Sublinear majority 3-coloring of digraphs arxiv solved 2016-08-10
Majority 3-coloring of tournaments arxiv open 2016-08-10
Majority 3-coloring of Eulerian digraphs arxiv open 2016-08-10
Majority 2-coloring recognition complexity arxiv partial 2016-08-10
Majority choosability constant for digraphs arxiv solved 2016-08-10
Fractional majority colouring weight below 3 arxiv partial 2016-08-10