Graph-theory open problems

Matija Bucić

Author (arXiv only) · 71 problems

Title Source Status Imp. Posted
Linear perimeter gap in vertex-transitive digraphs arxiv open 2026-02-18
Circumference equivalence vertex transitive digraphs arxiv open 2026-02-18
Longest cycles intersection in vertex transitive digraphs arxiv open 2026-02-18
Cycle lengths in vertex-transitive digraphs arxiv open 2026-02-18
Unimodal genus distribution arxiv open 2025-12-27
Log-concave genus distribution for triangulations arxiv open 2025-12-27
Maximum edge density of spectrally symmetric graphs arxiv open 2025-12-08
Exponential bound on optimal tea-sharing sequence length arxiv open 2025-09-22
Minimum negative p-energy at path graphs arxiv partial 2025-06-20
Infinite 3-edge-colourable edge-transitive cubic graphs arxiv solved 2025-06-10
Counterexamples in d-regular edge-colorable graphs arxiv solved 2025-06-10
Matching number drop by k(r−1) deletions arxiv open 2025-06-10
Lovász matching number in Cayley line hypergraphs arxiv disproved 2025-06-10
Positive square energy lower bound s⁺(G) ≥ n arxiv open 2025-06-08
Square energy sign in unicyclic odd-cycle graphs arxiv open 2025-06-08
s⁺(G) and s⁻(G) Extremal Characterization via Trees arxiv open 2025-06-08
s⁺(G) = n characterizes bipartite unicyclic graphs arxiv open 2025-06-08
Positive square energy ≥ n for large clique arxiv open 2025-06-08
Positive square energy of maximal planar graphs arxiv open 2025-06-08
Degree-four vertex in 5-critical crossing graphs arxiv open 2025-04-14
4-colorability with one crossing, degree ≥ 5 arxiv open 2025-04-14
Degree-four vertex in non-4-colorable C₀ graphs arxiv open 2025-04-14
Diamond generation of bichromatic-forbidding 4-candidates arxiv open 2025-04-14
Expected faces in G(n,p) random embedding logarithmic arxiv open 2025-04-09
Expected faces logarithmic for all G(n,p) arxiv open 2025-04-09
Logarithmic expected faces in dense graphs arxiv open 2025-04-09
Non-orientable random embedding faces of Kₙ arxiv open 2025-04-09
Non-orientable embedding faces below orientable arxiv open 2025-04-09
Square energy ⁴⁄₅n lower bound arxiv open 2024-09-26
Genus approximation hardness in spherical density regime arxiv open 2024-08-27
Tight clustering bound in treewidth-path strong product arxiv partial 2024-07-31
4/7 clustering exponent tight for strong products arxiv open 2024-07-31
Alon-Tarsi orientation with half out-degree arxiv open 2024-06-20
Matching reducing Alon-Tarsi number to ½Δ arxiv open 2024-06-20
Cop number √(n/k) bound for k-uniform hypergraphs arxiv open 2024-04-11
Linear face bound in random graph embeddings arxiv open 2023-03-30
Genus coefficient in Z₃-flow-critical density arxiv open 2022-12-04
Linear-growth graphs as tree boxtimes clique subgraphs arxiv open 2022-10-25
Linear expected faces in random orientable embeddings arxiv solved 2021-10-06
O(√n) balanced separator for U_t arxiv open 2021-09-01
Optimal degree bounds for c-crossing-critical graphs arxiv open 2021-05-05
Quadratic lower bound for map isomorphism arxiv open 2021-01-07
Superlinear lower bound for map isomorphism arxiv open 2021-01-07
Crossing number of Kₙ minus t-matching arxiv open 2020-09-07
Sharpness of ¼g cop-number exponent arxiv open 2020-05-21
Exponential flows in 3-edge-connected oriented graphs arxiv open 2020-05-19
Proper-incident short rainbow cycle bound arxiv open 2020-05-07
Short rainbow circuits in rank-(n-1) matroids arxiv partial 2020-05-07
Coloring abundance predicts reflexivity in cubic graphs arxiv open 2020-04-14
Hoppers existence for large Euler genus arxiv open 2020-02-01
Mixed-parity components in disconnected 4-coloring complexes arxiv open 2019-12-16
High-girth subgraphs with large χ_f arxiv open 2018-08-05
High-chromatic subgraph with large average degree arxiv open 2018-08-05
Algebraic connectivity supremum for graph-complement pairs arxiv partial 2018-06-18
Cop number partition of planar graphs arxiv open 2018-04-22
Cop number dichotomy for outerplanar graphs arxiv open 2018-04-22
Tightness of 3-cop capture time bound for planar graphs arxiv open 2018-04-22
Capture time bounds for genus-g graphs arxiv open 2018-04-22
Cop number √g growth rate by genus arxiv open 2017-10-31
Cop number of Riemannian surfaces by genus arxiv solved 2017-10-31
Cop convergence on Riemannian surfaces arxiv partial 2017-10-31
Worst fixed-genus surface for cop number arxiv open 2017-10-31
Cop number finiteness on bounded Riemannian surfaces arxiv partial 2017-10-31
Cops and Robbers on constant-curvature surfaces arxiv partial 2017-10-31
Obstructions for Diplanar Quartic Eulerian Digraphs arxiv open 2017-06-09
5/4 n TSP walk bound for subcubic graphs arxiv solved 2016-09-05
Extremal cone crossing number function arxiv partial 2016-08-27
Crossing bound for 2-page extension of 1-page drawing arxiv open 2016-08-27
Cone graph crossing f_s(k) k^(3/4) asymptotic arxiv open 2016-08-27
Maximum order of (c,s)-normal graphs arxiv open 2016-01-06
Normality of G(n,p) with high probability arxiv open 2016-01-06