Home » Subject

Graph Theory


Titlesort iconAuthor(s)Imp.¹Rec.²Topic » SubtopicPosted by
Graceful Tree Conjecture✭✭✭0Coloring » Labelingkintali
(m,n)-cycle coversCelmins; Preissmann✭✭✭0Basic G.T. » Cyclesmdevos
2-colouring a graph without a monochromatic maximum cliqueHoang; McDiarmid✭✭0Coloring » Vertex coloringJon Noel
3-Colourability of Arrangements of Great CirclesFelsner; Hurtado; Noy; Streinu✭✭1Topological G.T. » ColoringDavid Wood
3-Decomposition ConjectureArthur; Hoffmann-Ostenhof✭✭✭0arthur
3-Edge-Coloring ConjectureArthur; Hoffmann-Ostenhof✭✭✭1arthur
3-flow conjectureTutte✭✭✭0Coloring » Nowhere-zero flowsmdevos
4-connected graphs are not uniquely hamiltonianFleischner✭✭0Basic G.T. » Cyclesfhavet
4-flow conjectureTutte✭✭✭0Coloring » Nowhere-zero flowsmdevos
4-regular 4-chromatic graphs of high girthGrunbaum✭✭0Coloringmdevos
5-flow conjectureTutte✭✭✭✭0Coloring » Nowhere-zero flowsmdevos
5-local-tensionsDeVos✭✭0Topological G.T. » Coloringmdevos
57-regular Moore graph?Hoffman; Singleton✭✭✭0Algebraic G.T.mdevos
A generalization of Vizing's Theorem?Rosenfeld✭✭0Coloring » Edge coloringmdevos
A gold-grabbing gameRosenfeld✭✭0Graph Algorithmsmdevos
A homomorphism problem for flowsDeVos✭✭0Coloring » Nowhere-zero flowsmdevos
Acyclic edge-colouringFiamcik✭✭0Coloring » Edge coloringmdevos
Acyclic list colouring of planar graphs.Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena✭✭✭0Coloring » Vertex coloringfhavet
Ádám's ConjectureÁdám✭✭✭0Directed Graphsfhavet
Algorithm for graph homomorphismsFomin; Heggernes; Kratsch✭✭0Coloring » Homomorphismsjfoniok
Almost all non-Hamiltonian 3-regular graphs are 1-connectedHaythorpe✭✭1Basic G.T.mhaythorpe
Antichains in the cycle continuous orderDeVos✭✭0Coloring » Nowhere-zero flowsmdevos
Antidirected trees in digraphsAddario-Berry; Havet; Linhares Sales; Reed; Thomassé✭✭0Directed Graphsfhavet
Approximation ratio for k-outerplanar graphsBentz✭✭0jcmeyer
Approximation Ratio for Maximum Edge Disjoint Paths problemBentz✭✭0jcmeyer
Arc-disjoint directed cycles in regular directed graphsAlon; McDiarmid; Molloy✭✭0Directed Graphsfhavet
Arc-disjoint out-branching and in-branchingThomassen✭✭0Directed Graphsfhavet
Arc-disjoint strongly connected spanning subdigraphsBang-Jensen; Yeo✭✭0fhavet
Are almost all graphs determined by their spectrum?✭✭✭0mdevos
Are different notions of the crossing number the same?Pach; Tóth✭✭✭0Topological G.T. » Crossing numberscibulka
Are vertex minor closed classes chi-bounded?Geelen✭✭0Coloring » Vertex coloringmdevos
Asymptotic Distribution of Form of Polyhedra Rüdinger✭✭0Basic G.T.andreasruedinger
Barnette's ConjectureBarnette✭✭✭0Basic G.T. » CyclesRobert Samal
Beneš Conjecture (graph-theoretic form)Beneš✭✭✭0Vadim Lioubimov
Book Thickness of SubdivisionsBlankenship; Oporowski✭✭1David Wood
Bouchet's 6-flow conjectureBouchet✭✭✭0Coloring » Nowhere-zero flowsmdevos
Bounding the chromatic number of triangle-free graphs with fixed maximum degreeKostochka; Reed✭✭0Coloring » Vertex coloringAndrew King
Bounding the on-line choice number in terms of the choice numberZhu✭✭1Coloring » Vertex coloringJon Noel
Caccetta-Häggkvist ConjectureCaccetta; Häggkvist✭✭✭✭0Directed Graphsfhavet
Characterizing (aleph_0,aleph_1)-graphsDiestel; Leader✭✭✭0Infinite Graphsmdevos
Choice Number of k-Chromatic Graphs of Bounded OrderNoel✭✭1Coloring » Vertex coloringJon Noel
Choosability of Graph PowersNoel✭✭1Coloring » Vertex coloringJon Noel
Chords of longest cyclesThomassen✭✭✭0Basic G.T. » Cyclesmdevos
Chromatic number of $\frac{3}{3}$-power of graph✭✭0Iradmusa
Chromatic Number of Common GraphsHatami; Hladký; Kráľ; Norine; Razborov✭✭0David Wood
Chromatic number of random lifts of complete graphsAmit✭✭0Probabilistic G.T.DOT
Circular choosability of planar graphsMohar✭0Coloring » Homomorphismsrosskang
Circular coloring triangle-free subcubic planar graphsGhebleh; Zhu✭✭0Coloring » Vertex coloringmdevos
Circular colouring the orthogonality graphDeVos; Ghebleh; Goddyn; Mohar; Naserasr✭✭0Coloring » Vertex coloringmdevos
Circular flow number of regular class 1 graphsSteffen✭✭0Coloring » Nowhere-zero flowsEckhard Steffen

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

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

Syndicate content