Resolved Conjecture Timeline
Solved and disproved OPG and arXiv conjectures, from first claimed year to the review's resolution year.
Majority 1/k out-neighbour colouring digraphs
Majority Colourings of Digraphs
2016
->
2017
arxiv
disproved
1y
Majority choosability constant for digraphs
Majority Colourings of Digraphs
2016
->
2017
arxiv
solved
1y
Sublinear majority 3-coloring of digraphs
Majority Colourings of Digraphs
2016
->
2018
arxiv
solved
2y
Tree T-decomposition via maximum degree connectivity
Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
2016
->
2018
arxiv
disproved
2y
χ-Mader bound for oriented trees
Subdivisions in digraphs of large out-degree or large dichromatic number
2016
->
2020
arxiv
solved
4y
Block tree diameter gap beyond √(log n)
Random graphs from a block-stable class
2016
->
2022
arxiv
solved
6y
χ-boundedness of P₄-orientation forbiddance classes
$χ$-bounded families of oriented graphs
2016
->
2023
arxiv
solved
7y
Correspondence chromatic number planar graphs C₄–C₈-free
Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
2016
->
2024
arxiv
solved
8y
Token sliding connectivity by clique-tree degree
Token Sliding on Chordal Graphs
2016
->
2025
arxiv
disproved
9y
Chromatic concentration lower bound in G(n,p)
On the concentration of the chromatic number of random graphs
2017
->
2019
arxiv
solved
2y
Fractional 3-coloring of triangle-free planar requests
Do triangle-free planar graphs have exponentially many 3-colorings?
2017
->
2021
arxiv
disproved
4y
Tight constant for clique chromatic G(n,½)
Clique coloring of dense random graphs
2017
->
2023
arxiv
solved
6y
Cop number of Riemannian surfaces by genus
Notes on Cops and Robber game on graphs
2017
->
2024
arxiv
solved
7y
Erdős–Pósa O(k log k) bound for planar H-minors
A tight Erdős-Pósa function for wheel minors
2018
->
2018
arxiv
solved
0y
Sparse Strong EH-property Characterizes Forests
Caterpillars in Erdős-Hajnal
2018
->
2020
arxiv
solved
2y
Dense bipartite subgraph in triangle-free graphs
Separation choosability and dense bipartite induced subgraphs
2018
->
2025
arxiv
solved
7y
2-approximation for Cluster Vertex Deletion
Improved approximation algorithms for hitting 3-vertex paths
2019
->
2020
arxiv
solved
1y
Inducibility upper bound 1/e for non-trivial graphs
Edge-statistics on large graphs
2019
->
2020
arxiv
solved
1y
Polynomial minimal separators in (prism,pyramid,theta,turtle)-free graphs
Maximum independent sets in (pyramid, even hole)-free graphs
2019
->
2022
arxiv
solved
3y
Polynomial clique/independent set in bounded VC-dimension graphs
Bounded VC-dimension implies the Schur-Erdos conjecture
2019
->
2023
arxiv
solved
4y
Θ(√m) excess for hypergraph r-cuts
Hypergraph cuts above the average
2019
->
2024
arxiv
disproved
5y
Bounded-degree even-hole-free tree-width
On the tree-width of even-hole-free graphs
2020
->
2020
arxiv
solved
0y
Bounded treewidth for degree-t theta-triangle-free graphs
(Theta, triangle)-free and (even hole, $K_4$)-free graphs. Part 2 : bounds on treewidth
2020
->
2021
arxiv
solved
1y
√d log n bound for degenerate single-conflict chromatic number
Single-conflict colouring
2020
->
2021
arxiv
solved
1y
Induced wall in bounded-degree high tree-width graphs
On the tree-width of even-hole-free graphs
2020
->
2022
arxiv
solved
2y
Small hereditary class twin-width converse
Twin-width II: small classes
2020
->
2022
arxiv
disproved
2y
χ-bounded hereditary class without polynomial bound
Graphs of bounded cliquewidth are polynomially $χ$-bounded
2020
->
2022
arxiv
solved
2y
Degree-weighted independence vs Hall ratio gap
1-subdivisions, fractional chromatic number and Hall ratio
2020
->
2024
arxiv
solved
4y
Grundy Coloring FPT on K_{t,t}-free graphs
Grundy Coloring & friends, Half-Graphs, Bicliques
2020
->
2024
arxiv
solved
4y
Unavoidable G-dependence in blowup Ramsey prefactor
Extremal and Ramsey results on graph blowups
2020
->
2024
arxiv
solved
4y
Parameterized complexity of Partial Grundy Coloring
Grundy Coloring & friends, Half-Graphs, Bicliques
2020
->
2025
arxiv
solved
5y
Known forests for Esperet's polynomial χ-boundedness
Polynomial bounds for chromatic number. II. Excluding a star-forest
2021
->
2022
arxiv
disproved
1y
Friends-and-Strangers FS(X,Y) isolated-vertex cutoff coincidence
Typical and Extremal Aspects of Friends-and-Strangers Graphs
2021
->
2023
arxiv
solved
2y
Linear expected faces in random orientable embeddings
Random 2-cell embeddings of multistars
2021
->
2023
arxiv
solved
2y
Counting perfect matchings #P-hard for α=2 graphs
Exact Matching in Graphs of Bounded Independence Number
2022
->
2022
arxiv
solved
0y
Sufficiency of E, R, T for Generic Multiplicity Matrices
Counting Dope Matrices
2022
->
2022
arxiv
solved
0y
5-Coloring complexity for P₄+rP₃-free graphs
Complexity dichotomy for List-5-Coloring with a forbidden induced subgraph
2022
->
2023
arxiv
solved
1y
NP-hardness of List-k-Coloring on rP₃-free graphs
Complexity dichotomy for List-5-Coloring with a forbidden induced subgraph
2022
->
2023
arxiv
solved
1y
Polynomial saving in bipartite hereditary ex
Largest subgraph from a hereditary property in a random graph
2022
->
2024
arxiv
solved
2y
Near-acyclic r-free digraphs for r > 2n/3
Extremal results on feedback arc sets in digraphs
2022
->
2026
arxiv
solved
4y
Protrusive ordering not witnessed by 5 points
Ordering Candidates via Vantage Points
2023
->
2023
arxiv
solved
0y
n^{1/4} tight bound for non-averaging sets
Homogeneous structures in subset sums and non-averaging sets
2023
->
2024
arxiv
solved
1y
p-Centered coloring bound for minor-free graphs
The grid-minor theorem revisited
2023
->
2024
arxiv
solved
1y
Top-k eigenvalue limit points of d-regular graphs
The limit points of the top and bottom eigenvalues of regular graphs
2023
->
2024
arxiv
solved
1y
Polynomial degree-bounding for hereditary degree-bounded classes
Induced $C_4$-free subgraphs with large average degree
2023
->
2025
arxiv
solved
2y
Profile complexity of K_t-minor-free graphs
Neighborhood complexity of planar graphs
2023
->
2025
arxiv
solved
2y
BST Rotation Distance Computational Complexity
Shortest paths on polymatroids and hypergraphic polytopes
2023
->
2026
arxiv
solved
3y
Large dom implies ω̄-cluster in tournaments
Clique number of tournaments
2023
->
2026
arxiv
solved
3y
Threshold (1+ε)/n for Ω(n) distance reconstruction
Reconstructing a point set from a random subset of its pairwise distances
2023
->
2026
arxiv
solved
3y
Induced Turán number for C_{2ℓ} in sparse graphs
The largest subgraph without a forbidden induced subgraph
2024
->
2024
arxiv
solved
0y
Logarithmic treewidth of (even hole, Kₜ)-free graphs
Tree independence number I. (Even hole, diamond, pyramid)-free graphs
2024
->
2024
arxiv
solved
0y
Polynomial η-boundedness of M_t-free graphs
Hitting all maximum stable sets in $P_5$-free graphs
2024
->
2025
arxiv
solved
1y
Characterisation of maximum circular sorting permutations
Circular sorting
2025
->
2025
arxiv
disproved
0y
Counterexamples in d-regular edge-colorable graphs
A Counterexample to a Conjecture of Lovász
2025
->
2025
arxiv
solved
0y
Infinite 3-edge-colourable edge-transitive cubic graphs
A Counterexample to a Conjecture of Lovász
2025
->
2025
arxiv
solved
0y
Lovász matching number in Cayley line hypergraphs
A Counterexample to a Conjecture of Lovász
2025
->
2025
arxiv
disproved
0y
Start years prefer references marked original, then the earliest bibliography year, then the OPG posting year. For arXiv-extracted conjectures, the source-paper year is used when no attribution year is recorded. End years prefer proof/counterexample citations, then the earliest cited resolving item in the literature review.