Graph-theory open problems

Thomassé, Stéphan

Author · 71 problems

Title Source Status Imp. Posted
Directed path of length twice the minimum outdegree opg partial ★★★ 2013-02-28
Antidirected trees in digraphs opg partial ★★ 2013-02-26
Active path characterisation in complete graphs arxiv open 2025-10-10
Active vertices in optimal lollipop cycle arxiv open 2025-10-10
Linear chords in minimum-degree-3 cycles arxiv partial 2025-10-10
MIS quasipolynomial time for planar induced-minor-free arxiv open 2025-12-31
Non-antidirected paths at semidegree k/2 arxiv open 2025-03-29
O(ℓ√log ℓ) bound for cyclic Kℓ-minors arxiv open 2025-10-10
Open: $f(\mathrm{OPT})$-approximation for largest (general) complete minor arxiv open 2025-05-09
Constant-factor approximation for RFCPP arxiv open 2024-01-11
Left-maximal DFS-tree complexity in digraphs arxiv open 2024-01-11
MIS tractability in bounded-iocp graphs arxiv open 2024-02-16
O(log n) forward cover for strong digraphs arxiv open 2024-01-11
Optimal balanced bi-tree size constant arxiv open 2024-01-11
Optimal FCPP approximation ratio in digraphs arxiv open 2024-01-11
Polynomial MIS in 𝒪_k-free graphs arxiv open 2024-02-16
Twin-width bound for K_{t,t}-free O_k-free graphs arxiv open 2024-02-16
Maximum D(n,k) asymptotics in IS reconfiguration arxiv open 2023-01-05
MWIS QPTAS in subdivision-of-forest-free graphs arxiv open 2023-11-14
Parameterized complexity of separable index arxiv open 2023-08-06
Polynomial separable index for pattern-avoiding permutations arxiv open 2023-08-06
Super-cubic diameter of 4-configuration graph arxiv open 2023-01-05
Delineation of unit segment graphs by twin-width arxiv partial 2022-04-01
Explicit group construction with infinite twin-width arxiv open 2022-07-15
Twin-width approximation for unordered graphs arxiv partial 2022-05-31
Twin-width of matrices over infinite fields arxiv open 2022-09-24
Twin-width vs Queue Number Separation arxiv open 2022-07-15
Uniform twin-width strictly stronger than twin-width arxiv open 2022-07-15
Connected k-domination no-kernel at twin-width 4 arxiv open 2021-09-14
Convex unit distance realizability of G_k arxiv open 2021-06-02
FPT FO model checking superclass of twin-width arxiv partial 2021-10-25
MIS vs. Min Dominating Set approximability gap arxiv partial 2021-02-12
Polynomial expansion implies bounded twin-width arxiv open 2021-10-25
Polynomial minimal separators via k-creature exclusion arxiv disproved 2021-12-28
Bounded treewidth for degree-t theta-triangle-free graphs arxiv solved 2020-10-27
Bounded treewidth for even-hole K₄ diamond-free graphs arxiv partial 2020-10-27
Bounded twin-width for polynomial expansion classes arxiv open 2020-06-17
Cliquewidth of triangle, S₁,₂,₃-free graphs arxiv open 2020-10-27
Combinatorial MIS algorithm for perfect graphs arxiv partial 2020-01-16
FPT Algorithm for MWIS in (Long-Hole, k-Prism)-Free Graphs arxiv open 2020-01-16
MIS approximation exponent in H-free graphs arxiv open 2020-04-25
MIS complexity for (even hole, K₄)-free graphs arxiv open 2020-10-27
MIS complexity for S_{i,j,k}-free graphs with P₇ arxiv partial 2020-10-27
MIS sub-polynomial approximation in H-free graphs arxiv open 2020-04-25
Small hereditary class twin-width converse arxiv disproved 2020-06-17
Combinatorial MIS algorithm on perfect graphs arxiv open 2019-10-06
FPT candidates for H-free MIS nearly all tractable arxiv open 2019-09-18
FPT MIS in P(t,t,t,t)-free graphs arxiv open 2019-09-18
MIS complexity in even-hole-free graphs arxiv partial 2019-12-24
MIS dichotomy for path- and claw-subdivision-free graphs arxiv partial 2019-09-18
MIS FPT in Pℓ(t)-free Graphs arxiv open 2019-09-18
MIS parameterized complexity in H-free graphs arxiv partial 2019-09-18
Polynomial minimal separators in (prism,pyramid,theta,turtle)-free graphs arxiv solved 2019-12-24
Polynomial minimal separators in odd-hole-free graphs arxiv partial 2019-12-24
T-decomposition by leaf count of trees arxiv open 2019-07-26
Clique or dense bipartite subgraph in high-degree graphs arxiv partial 2018-12-04
Dense bipartite subgraph in triangle-free graphs arxiv solved 2018-12-04
Large Girth Dense Bipartite Induced Subgraph arxiv open 2018-12-04
Polynomial domination bound in triangle-free digraphs arxiv open 2018-04-27
Separation choosability grows with minimum degree arxiv open 2018-12-04
ℤ₅-antisymmetric flow in k-edge-connected digraphs arxiv open 2018-02-07
Dominating number forcing in tournament subtournaments arxiv open 2017-03-15
Large domination number forces Sᵢ subtournament arxiv open 2017-03-15
VC-dimension dichotomy for identifying codes approximation arxiv open 2017-04-14
Closure of δ⁺-maderian digraphs under disjoint union arxiv open 2016-10-04
Exact value of mader_χ̄(K̄ₙ) arxiv open 2016-10-04
Tree T-decomposition via maximum degree connectivity arxiv disproved 2016-06-30
TT_k Subdivision via Minimum Semidegree arxiv open 2016-10-04
δ⁺-Maderian property for oriented trees arxiv open 2016-10-04
κ-maderianness of strongly connected digraphs arxiv partial 2016-10-04
χ-Mader bound for oriented trees arxiv solved 2016-10-04