Open Problems


TitleAuthor(s)sort iconImp.¹Rec.²Area » Topic » SubtopicPosted by
Mixing Circular ColouringsBrewster; Noel1Graph Theory » Coloring » Vertex coloringJon Noel
Cycles in Graphs of Large Chromatic NumberBrewster; McGuinness; Moore; Noel✭✭0Graph Theory » Coloring » Vertex coloringJon Noel
Bouchet's 6-flow conjectureBouchet✭✭✭0Graph Theory » Coloring » Nowhere-zero flowsmdevos
List Total Colouring ConjectureBorodin; Kostochka; Woodall✭✭0Graph Theory » ColoringJon Noel
The Borodin-Kostochka ConjectureBorodin; Kostochka✭✭0Graph TheoryAndrew King
Acyclic list colouring of planar graphs.Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena✭✭✭0Graph Theory » Coloring » Vertex coloringfhavet
Degenerate colorings of planar graphsBorodin✭✭✭0Graph Theory » Topological G.T. » Coloringmdevos
Switching reconstruction of digraphsBondy; Mercier✭✭0Graph Theoryfhavet
Cyclic spanning subdigraph with small cyclomatic numberBondy✭✭0Graph Theory » Directed Graphsfhavet
Few subsequence sums in Z_n x Z_nBollobas; Leader✭✭0Number Theory » Combinatorial N.T.mdevos
Fixed-point logic with countingBlass✭✭0Logic » Finite Model Theorydberwanger
Book Thickness of SubdivisionsBlankenship; Oporowski✭✭1Graph TheoryDavid Wood
Signing a graph to have small magnitude eigenvaluesBilu; Linial✭✭0Graph Theorymdevos
Distribution and upper bound of mimic numbersBhattacharyya✭✭1Number Theory » Analytic N.T.facility_cttb@i...
The Bermond-Thomassen ConjectureBermond; Thomassen✭✭0Graph Theory » Directed GraphsJS
Linial-Berge path partition dualityBerge; Linial✭✭✭0Graph Theory » Coloringberger
The Berge-Fulkerson conjectureBerge; Fulkerson✭✭✭✭0Graph Theory » Basic G.T. » Matchingsmdevos
Approximation Ratio for Maximum Edge Disjoint Paths problemBentz✭✭0Graph Theoryjcmeyer
Approximation ratio for k-outerplanar graphsBentz✭✭0Graph Theoryjcmeyer
Finding k-edge-outerplanar graph embeddingsBentz✭✭0Graph Theoryjcmeyer
Shuffle-Exchange Conjecture (graph-theoretic form)Beneš; Folklore; Stone✭✭✭0Graph TheoryVadim Lioubimov
Shuffle-Exchange ConjectureBeneš; Folklore; Stone✭✭✭0CombinatoricsVadim Lioubimov
Beneš ConjectureBeneš✭✭✭0CombinatoricsVadim Lioubimov
Beneš Conjecture (graph-theoretic form)Beneš✭✭✭0Graph TheoryVadim Lioubimov
The robustness of the tensor productBen-Sasson; Sudan✭✭✭0Theoretical Comp. Sci. » Coding Theoryormeir
Total Colouring ConjectureBehzad✭✭✭0Graph Theory » ColoringIradmusa
Barnette's ConjectureBarnette✭✭✭0Graph Theory » Basic G.T. » CyclesRobert Samal
Forcing a $K_6$-minorBarát ; Joret; Wood✭✭0Graph Theory » Basic G.T. » MinorsDavid Wood
Arc-disjoint strongly connected spanning subdigraphsBang-Jensen; Yeo✭✭0Graph Theoryfhavet
Decomposing k-arc-strong tournament into k spanning strong digraphsBang-Jensen; Yeo✭✭0Graph Theory » Directed Graphs » Tournamentsfhavet
Minimal graphs with a prescribed number of spanning treesAzarija; Skrekovski✭✭1Graph Theoryazi
Vertex Cover Integrality GapAtserias✭✭0Logic » Finite Model Theorydberwanger
Strong 5-cycle double cover conjectureArthur; Hoffmann-Ostenhof✭✭✭1Graph Theory » Basic G.T. » Cyclesarthur
3-Decomposition ConjectureArthur; Hoffmann-Ostenhof✭✭✭0Graph Theoryarthur
Cycle Double Covers Containing Predefined 2-Regular SubgraphsArthur; Hoffmann-Ostenhof✭✭✭0Graph Theoryarthur
Crossing sequencesArchdeacon; Bonnington; Siran✭✭0Graph Theory » Topological G.T. » Crossing numbersRobert Samal
Good Edge LabelingsAraújo; Cohen; Giroire; Havet✭✭0Graph Theory » Coloring » LabelingDOT
Odd perfect numbersAncient/folklore✭✭✭1Number Theoryazi
Which homology 3-spheres bound homology 4-balls?Ancient/folklore✭✭✭✭0Topologyrybu
Fundamental group torsion for subsets of Euclidean 3-spaceAncient/folklore✭✭0Topologyrybu
Chromatic number of random lifts of complete graphsAmit✭✭0Graph Theory » Probabilistic G.T.DOT
Hamilton decomposition of prisms over 3-connected cubic planar graphsAlspach; Rosenfeld✭✭0Graph Theory » Basic G.T. » Cyclesfhavet
Decomposing an even tournament in directed paths.Alspach; Mason; Pullman✭✭✭0Graph Theory » Directed Graphs » Tournamentsfhavet
Obstacle number of planar graphsAlpert; Koch; Laison1Graph TheoryAndrew King
Rendezvous on a lineAlpern✭✭✭0Unsortedmdevos
Even vs. odd latin squaresAlon; Tarsi✭✭✭0Combinatoricsmdevos
Nearly spanning regular subgraphsAlon; Mubayi✭✭✭0Graph Theory » Basic G.T.mdevos
Arc-disjoint directed cycles in regular directed graphsAlon; McDiarmid; Molloy✭✭0Graph Theory » Directed Graphsfhavet
The Alon-Tarsi basis conjectureAlon; Linial; Meshulam✭✭0Combinatorics » Matricesmdevos
Ramsey properties of Cayley graphsAlon✭✭✭0Graph Theory » Algebraic G.T.mdevos
Syndicate content