Graph-theory open problems

Marthe Bonamy

Author (arXiv only) · 55 problems

Title Source Status Imp. Posted
Pivot Gray code for all spanning trees arxiv open 2026-03-30
Bounded domination-to-2-independence ratio characterization arxiv open 2026-01-21
γ(G) ≤ h(α₂(G)) graph class characterization arxiv open 2026-01-21
Modular chromatic index of 0ₖ-graphs arxiv open 2025-12-05
Dom-Enum polynomial in Sₜ-free incomparability graphs arxiv open 2025-11-26
Dom-Enum in co-bipartite H-free incomparability graphs arxiv open 2025-11-26
Sparse graph cut chromatic threshold arxiv disproved 2025-10-02
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
χ-boundedness of radius-1 merge-width graphs arxiv open 2025-06-16
Merge-width characterised by FO-transduction neighbourhood complexity arxiv open 2025-06-16
Quasi-minor gap infimum for Kₜ arxiv open 2025-03-13
Kempe equivalence of colorings in Kₜ-minor-free graphs arxiv open 2025-03-13
Constant domination-packing ratio per graph class arxiv partial 2025-03-07
Characterization of bounded γ/ρ graph classes arxiv partial 2025-03-07
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
MIS tractability in bounded-iocp graphs arxiv open 2024-02-16
Linear strongly-separating path system constant arxiv open 2023-10-10
Linear rainbow path cover of edge-colored graphs arxiv open 2023-10-10
Odd-Δ planar linear arboricity with matching arxiv partial 2023-02-26
List Total Coloring χ″ℓ ≤ Δ+2 arxiv open 2022-12-09
R-burnability of trees with bounded growth arxiv open 2022-03-04
Polynomial Kempe connectivity in degenerate graphs arxiv open 2021-12-04
Zombie number invariance under leaf attachment arxiv open 2021-06-03
Zombie number increase via subdivision arxiv open 2021-06-03
χ_ISC strict inequality for non-complete graphs arxiv open 2021-01-06
Fractional vertex-arboricity ≤ 2 planar graphs arxiv open 2020-09-25
χ-bounded hereditary class without polynomial bound arxiv solved 2020-07-07
Independence ratio of Mycielski graphs arxiv open 2020-03-23
fvs–face-packing ratio in planar graphs arxiv open 2019-12-03
χ-boundedness of binary matroids excluding I_s and PG(1,2) arxiv partial 2019-11-13
GI complexity dichotomy for (H₁,H₂)-free graphs arxiv open 2019-09-03
Graph Isomorphism FPT by Clique-Width arxiv open 2019-09-03
Clique-Width Boundedness for Five Open Pairs arxiv open 2019-09-03
Disjoint avoidable Pₖ pairs existence arxiv disproved 2019-08-10
Avoidable non-path family existence arxiv partial 2019-08-10
Polynomial recognition of Switchable graphs arxiv open 2019-04-12
Sublinear round complexity for distributed coloring arxiv open 2018-12-19
Randomized round complexity of Δ-list-coloring arxiv open 2018-12-19
Glauber (Δ+1)-colouring mixing without Δ = o(n) arxiv open 2018-11-30
Exponent gap for frozen (Δ+1)-colourings arxiv open 2018-11-30
Sparsity of clique-bounded critical graphs arxiv partial 2018-10-15
Optimal ε for sparse-neighbourhood chromatic bound arxiv partial 2018-10-15
List chromatic bound via sublinear clique condition arxiv solved 2018-03-02
List-chromatic Reed bound arxiv open 2018-03-02
Independent Feedback Vertex Set linear forest complexity arxiv open 2017-07-28
WSK validity for 5-colorings of triangular lattice arxiv partial 2016-09-22
Gallai path decomposition beyond odd semi-cliques arxiv partial 2016-09-20
Token sliding connectivity by clique-tree degree arxiv disproved 2016-05-02
η(G) ≥ 2n for 2-connected graphs arxiv open 2016-02-16