Home » Subject

Graph Theory


TitleAuthor(s)sort iconImp.¹Rec.²Topic » SubtopicPosted by
Decomposing eulerian graphs✭✭✭0Basic G.T. » Cyclesmdevos
Consecutive non-orientable embedding obstructions✭✭✭0Topological G.T. » GenusBruce Richter
The Crossing Number of the Complete Graph✭✭✭0Topological G.T. » Crossing numbersRobert Samal
Triangle free strongly regular graphs✭✭✭0Algebraic G.T.mdevos
Graceful Tree Conjecture✭✭✭0Coloring » Labelingkintali
Oriented chromatic number of planar graphs✭✭0Coloring » Vertex coloringRobert Samal
Edge list coloring conjecture✭✭✭0Coloring » Edge coloringtchow
Shannon capacity of the seven-cycle✭✭✭0tchow
Odd cycles and low oddness✭✭0Gagik
Covering powers of cycles with equivalence subgraphs✭0Andrew King
Matching cut and girth✭✭0w
The Bollobás-Eldridge-Catlin Conjecture on graph packing✭✭✭0Extremal G.T.asp
Are almost all graphs determined by their spectrum?✭✭✭0mdevos
Monochromatic vertex colorings inherited from Perfect Matchings✭✭✭1Mario Krenn
Chromatic number of $\frac{3}{3}$-power of graph✭✭0Iradmusa
Large induced forest in a planar graph.Abertson; Berman✭✭0Topological G.T.fhavet
Coloring and immersionAbu-Khzam; Langston✭✭✭1Coloring » Vertex coloringmdevos
Ádám's ConjectureÁdám✭✭✭0Directed Graphsfhavet
Antidirected trees in digraphsAddario-Berry; Havet; Linhares Sales; Reed; Thomassé✭✭0Directed Graphsfhavet
Strong matchings and coversAharoni✭✭✭0Infinite Graphsmdevos
Strong colorabilityAharoni; Alon; Haxell✭✭✭0Coloring » Vertex coloringberger
PTAS for feedback arc set in tournamentsAilon; Alon✭✭0Graph Algorithmsfhavet
Crossing numbers and coloringAlbertson✭✭✭0Topological G.T. » Crossing numbersmdevos
Partial List ColoringAlbertson; Grossman; Haas✭✭✭0Coloring » Vertex coloringIradmusa
List Colourings of Complete Multipartite Graphs with 2 Big PartsAllagan✭✭1Coloring » Vertex coloringJon Noel
Ramsey properties of Cayley graphsAlon✭✭✭0Algebraic G.T.mdevos
Splitting a digraph with minimum outdegree constraintsAlon✭✭✭0Directed Graphsfhavet
List chromatic number and maximum degree of bipartite graphsAlon✭✭0Coloring » Vertex coloringfhavet
Arc-disjoint directed cycles in regular directed graphsAlon; McDiarmid; Molloy✭✭0Directed Graphsfhavet
Nearly spanning regular subgraphsAlon; Mubayi✭✭✭0Basic G.T.mdevos
Obstacle number of planar graphsAlpert; Koch; Laison✭1Andrew King
Decomposing an even tournament in directed paths.Alspach; Mason; Pullman✭✭✭0Directed Graphs » Tournamentsfhavet
Hamilton decomposition of prisms over 3-connected cubic planar graphsAlspach; Rosenfeld✭✭0Basic G.T. » Cyclesfhavet
Chromatic number of random lifts of complete graphsAmit✭✭0Probabilistic G.T.DOT
Good Edge LabelingsAraújo; Cohen; Giroire; Havet✭✭0Coloring » LabelingDOT
Crossing sequencesArchdeacon; Bonnington; Siran✭✭0Topological G.T. » Crossing numbersRobert Samal
Strong 5-cycle double cover conjectureArthur; Hoffmann-Ostenhof✭✭✭1Basic G.T. » Cyclesarthur
3-Decomposition ConjectureArthur; Hoffmann-Ostenhof✭✭✭0arthur
Cycle Double Covers Containing Predefined 2-Regular SubgraphsArthur; Hoffmann-Ostenhof✭✭✭0arthur
3-Edge-Coloring ConjectureArthur; Hoffmann-Ostenhof✭✭✭1arthur
Minimal graphs with a prescribed number of spanning treesAzarija; Skrekovski✭✭1azi
Arc-disjoint strongly connected spanning subdigraphsBang-Jensen; Yeo✭✭0fhavet
Decomposing k-arc-strong tournament into k spanning strong digraphsBang-Jensen; Yeo✭✭0Directed Graphs » Tournamentsfhavet
Forcing a $K_6$-minorBarát ; Joret; Wood✭✭0Basic G.T. » MinorsDavid Wood
Barnette's ConjectureBarnette✭✭✭0Basic G.T. » CyclesRobert Samal
Total Colouring ConjectureBehzad✭✭✭0ColoringIradmusa
Beneš Conjecture (graph-theoretic form)Beneš✭✭✭0Vadim Lioubimov
Shuffle-Exchange Conjecture (graph-theoretic form)Beneš; Folklore; Stone✭✭✭0Vadim Lioubimov
Approximation Ratio for Maximum Edge Disjoint Paths problemBentz✭✭0jcmeyer
Approximation ratio for k-outerplanar graphsBentz✭✭0jcmeyer

Imp.¹: Importance (Low ✭, Medium ✭✭, High ✭✭✭, Outstanding ✭✭✭✭)
Rec.²: Recommended for undergraduates.

Note: Resolved problems from this section may be found in Solved problems.

Syndicate content