Graph-theory open problems

Sepehr Hajebi

Author (arXiv only) · 84 problems

Title Source Status Imp. Posted
χ-boundedness of sun-free graphs arxiv open 2026-03-08
Unavoidable induced subgraphs of large treewidth arxiv disproved 2026-02-18
3-colouring diameter-2 graphs quasi-polynomial time arxiv open 2026-01-19
Induced C_{2t}-saturation edge-addition existence arxiv open 2025-06-02
Polynomial size even-cycle induced saturation arxiv open 2025-06-02
Intersectionwise χ-guarding class characterization arxiv open 2025-03-31
χ-boundedness via odd cycle exclusion arxiv solved 2025-03-25
Cycle orientations in high chromatic high out-degree digraphs arxiv solved 2025-03-25
Digraph H-subgraph via χ and out-degree arxiv open 2025-03-25
Directed chromatic threshold for digraph subgraphs arxiv open 2025-03-25
Unavoidable language in padded strings arxiv open 2024-11-26
MWIS polynomial-time on even-hole-free graphs arxiv open 2024-07-12
Polynomial-time Coloring on even-hole-free graphs arxiv open 2024-07-12
Bounded tree-α in (even hole, diamond)-free graphs arxiv partial 2024-02-22
Logarithmic treewidth of (even hole, Kₜ)-free graphs arxiv solved 2024-02-22
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
η-boundedness for H-free graphs arxiv partial 2024-01-16
η-boundedness of Pₜ-free graphs arxiv open 2024-01-16
Polynomial η-bound for P₅-free graphs arxiv open 2024-01-16
Polynomial η-boundedness of M_t-free graphs arxiv solved 2024-01-16
η-boundedness for two-star unions arxiv open 2024-01-16
Joined Union Decomposition of Cayley Graphs arxiv partial 2024-01-11
Primeness of Cayley graphs over finite rings arxiv partial 2024-01-11
Primeness of tensor products of complete graphs arxiv open 2024-01-11
Polynomial 3-coloring for path-component-free graphs arxiv open 2023-11-09
k-Coloring dichotomy for H-free graphs arxiv open 2023-11-09
Cleanness of t-clock-free graphs arxiv open 2023-11-09
Clean H-free classes from finite families arxiv partial 2023-11-07
Linear pure pair in sparse H-free graphs arxiv open 2023-10-29
Stronger coherence condition for pure pairs arxiv open 2023-10-29
Happy triples extremal bound for l < k/2 arxiv open 2023-09-11
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
χ-finite families characterizing dichromatic boundedness arxiv open 2023-06-07
Δ(1,m,m') hero status for degree-4 oriented stars arxiv open 2023-06-07
Δ(1,2,2) hero status in {K₁+P⃗₂}-free digraphs arxiv open 2023-06-07
Grassmannian subvariety for claw-free incomparability graphs arxiv open 2023-05-18
Polynomial χ-boundedness for H-free forest classes arxiv partial 2023-03-22
Nondominating broom copy in χ-bounded graphs arxiv open 2023-03-22
Chordal modulator characterization for even-hole-free graphs arxiv partial 2023-01-28
Bounded treewidth for (C₄, diamond, theta, prism)-free graphs arxiv open 2022-10-21
Polynomial χ-boundedness for forest-free graphs arxiv partial 2022-10-02
χ-boundedness with clique number 3 and triangle-free subgraphs arxiv open 2022-09-15
χ-boundedness for odd-cycle-free digraphs arxiv open 2022-09-15
Logarithmic treewidth via four forbidden families arxiv open 2022-09-07
5-Coloring complexity for P₄+rP₃-free graphs arxiv solved 2022-08-30
NP-hardness of List-k-Coloring on rP₃-free graphs arxiv solved 2022-08-30
ε-restricted union cover for H-free graphs arxiv open 2022-08-03
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
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
Maximum symmetric intersecting family in [k]^n arxiv open 2020-07-31
Largest symmetric intersecting families set-intersecting arxiv open 2020-07-31
Polynomial gain on symmetric intersecting vector families arxiv open 2020-07-31
Forest-filleting of coherent ideals arxiv open 2020-06-02
Polynomial algorithm for fixed-k induced detours arxiv open 2020-05-26
Prime p-entropic matroids are F_p-representable arxiv open 2019-09-26
Disproportionate division requires 2n−2 cuts arxiv open 2019-09-16
Disproportionate bipartition of measures on S¹ arxiv open 2019-09-16
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
Sparse Strong EH-property Characterizes Forests arxiv solved 2018-10-01
3-colourability of ternary graphs arxiv open 2018-09-28
Polynomial 3-coloring for P_t-free graphs arxiv partial 2018-07-02
Polynomial δ Dependence in Rödl's Theorem arxiv partial 2018-03-09
Maximum tight skew partitions in perfect graphs arxiv open 2017-07-12