Graph-theory open problems

Dvorak, Zdenek

Author · 86 problems

Title Source Status Imp. Posted
Star chromatic index of complete graphs opg open ★★ 2010-11-16
Star chromatic index of cubic graphs opg partial ★★ 2010-11-16
Bounded domination-to-2-independence ratio characterization arxiv open 2026-01-21
γ(G) ≤ h(α₂(G)) graph class characterization arxiv open 2026-01-21
χ = χ_ℓ = χ_DP threshold for ω = Δ−1 arxiv open 2026-03-15
4-color bound for cubic 2-homogeneous coloring arxiv open 2025-11-04
4-colorability of cycles union K₄s arxiv open 2025-11-04
4-colorability with one crossing, degree ≥ 5 arxiv open 2025-04-14
Active path characterisation in complete graphs arxiv open 2025-10-10
Active vertices in optimal lollipop cycle arxiv open 2025-10-10
Almost-ℤ₂²- and ℤ₄-connectedness of bicritical snarks arxiv open 2025-11-04
Degree-four vertex in 5-critical crossing graphs 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
Finite exceptions to 2-homogeneous cubic coloring arxiv open 2025-11-04
Fractional 19/7-colorability of subcubic triangle-free graphs arxiv open 2025-03-28
Linear chords in minimum-degree-3 cycles arxiv partial 2025-10-10
Monochromatic non-nested matching in 2-edge-colored Kₘ arxiv partial 2025-11-04
Non-realizable colorings for X-rooted Kₖ-minor-free graphs arxiv open 2025-04-10
Non-zero P_G coefficient in random 4-regular graphs arxiv open 2025-11-04
O(ℓ√log ℓ) bound for cyclic Kℓ-minors arxiv open 2025-10-10
Partition polytope diameter ⌈4κ₁/3⌉ bound arxiv open 2025-07-28
Strong 6-edge-coloring of diamond-free claw-free cubics arxiv open 2025-11-04
½-flow-pair existence in bridgeless graphs arxiv open 2025-11-04
5-choosability equals 5-colorability on torus arxiv open 2024-07-26
5-choosability equals 6-criticality on torus arxiv open 2024-07-26
Edge-width four torus 5-choosability arxiv open 2024-07-26
No critical prism-canvas at spacing ≥ 5 arxiv open 2024-07-26
4-coloring extension via well-separated long faces arxiv open 2023-12-20
NP-hardness of square root for planar graphs arxiv open 2023-07-13
Polynomial-time precoloring extension in planar near-Eulerian-triangulations arxiv open 2023-12-20
Product structure open problem for sublinear separators arxiv partial 2023-09-27
Product structure with bounded tree-depth separators arxiv open 2023-09-27
Random Graph Correspondence Chromatic Number Θ(n/log n) arxiv open 2023-07-27
Genus coefficient in Z₃-flow-critical density arxiv open 2022-12-04
Tight asymptotic dimension bound for intersection graphs arxiv open 2022-10-04
4-coloring extension for near-triangulations arxiv partial 2021-10-25
FO minimization PTAS in treewidth-fragile classes arxiv open 2021-10-09
FO-definable maximization in nowhere-dense classes arxiv open 2021-10-09
Optimal degree bounds for c-crossing-critical graphs arxiv open 2021-05-05
Planar near-cubic 5-distance coloring cone membership arxiv open 2021-10-25
Polynomial weak coloring numbers for thin intersection graphs arxiv open 2021-04-07
PTAS for weighted Minimum Vertex Cover in fragile classes arxiv open 2021-05-04
Subexponential lower bound for triangle-free planar 3-colorings arxiv open 2021-08-28
Sublinear separators imply fractional treewidth-fragility arxiv open 2021-10-09
Weak diameter 2-coloring near non-triangular faces arxiv open 2021-11-13
Bounded Expansion via Hall Ratio in Shallow Minors arxiv open 2020-01-30
Conflict k-colouring on surfaces of genus g arxiv open 2020-10-09
Degree-weighted independence vs Hall ratio gap arxiv solved 2020-01-30
Distant precoloring extension in plane triangle-free graphs arxiv open 2020-04-15
Exact value of separator exponent b_ε arxiv open 2020-07-07
Linear diameter of 6-recoloring, girth-5 planar graphs arxiv partial 2020-06-16
Linear diameter of planar graph reconfigurations arxiv partial 2020-02-13
Linear-time 3-coloring output on surfaces arxiv open 2020-11-05
One-sided sublinear separator expansion equality arxiv open 2020-07-07
Polynomial-time 4-colorability on fixed surfaces arxiv open 2020-08-04
Tame representation for polynomial strong coloring numbers arxiv open 2020-01-06
Tame representation impossible for bounded col_r graphs arxiv open 2020-01-06
χ_f to Hall ratio gap growth rate arxiv partial 2020-01-30
√d log n bound for degenerate single-conflict chromatic number arxiv solved 2020-10-09
11/3 non-tight fractional chromatic bound for {C₄,C₅}-free planar arxiv partial 2019-07-14
Characterization of (CC) for coloring parameters arxiv open 2019-02-26
Fractional chromatic number of {C₄,C₅}-free planar graphs arxiv partial 2019-07-14
Independence number lower bound in K_{t+1}-minor-free graphs arxiv open 2019-07-30
MR_t(s,k) bound for Ks-free graphs arxiv open 2019-07-30
Optimal cycle count bound via edge number arxiv open 2019-07-28
PTAS for monotone FO optimization via local search arxiv partial 2019-01-07
5/6 bound induced 2-degenerate triangle-free planar arxiv open 2018-02-19
Constant-size separator M in bounded expansion arxiv open 2018-02-09
Improved hub color ratio in girth-five wheels arxiv open 2018-09-14
Induced 2-degenerate ⅞ subgraph triangle-free planar arxiv open 2018-02-19
ε-flexibility of d-degenerate graphs with (d+1)-lists arxiv partial 2018-11-17
Additive chromatic approximation gap in K_k-minor-free arxiv open 2017-07-12
Chromatic number of Kₖ-free bounded treewidth graphs arxiv open 2017-06-09
col★ characterization for minor-closed classes arxiv open 2017-10-07
Fractional 3-coloring of triangle-free planar requests arxiv disproved 2017-09-19
Independence number n/4 in planar graphs arxiv open 2017-02-09
Independent set APX-hardness without sublinear separators arxiv open 2017-04-01
List-coloring bounded obstruction for girth-5 planar graphs arxiv open 2017-07-05
Thin overlays without bounded-degree assumption arxiv open 2017-04-01
Triangle-free χ additive approximation in minor-closed arxiv open 2017-07-12
3-Choosability of Planar Graphs Forbidding C₄–C₆ arxiv open 2016-10-08
4-colorability on fixed surfaces complexity arxiv open 2016-03-04
5/4 n TSP walk bound for subcubic graphs arxiv solved 2016-09-05
Correspondence chromatic number planar graphs C₄–C₈-free arxiv solved 2016-10-08
χ_f bound 3 - 3/(n+1) for planar triangle-free arxiv open 2016-06-20