Home » Subject

Graph Theory


TitleAuthor(s)Imp.¹Rec.²sort iconTopic » SubtopicPosted by
Monochromatic reachability or rainbow trianglesSands; Sauer; Woodrow✭✭✭0Directed Graphs » Tournamentsmdevos
Crossing sequencesArchdeacon; Bonnington; Siran✭✭0Topological G.T. » Crossing numbersRobert Samal
Compatible Matching ConjectureWood✭✭0Topological G.T. » DrawingsRobert Samal
Short cycle coversAlon; Tarsi✭✭0Basic G.T. » CyclesRobert Samal
Circular colouring the orthogonality graphDeVos; Ghebleh; Goddyn; Mohar; Naserasr✭✭0Coloring » Vertex coloringmdevos
Middle levels problemErdos✭✭0Basic G.T. » Cyclestchow
Frankl's union-closed sets conjectureFrankl✭✭0Hypergraphstchow
Edge list coloring conjecture✭✭✭0Coloring » Edge coloringtchow
Seymour's r-graph conjectureSeymour✭✭✭0Coloring » Edge coloringmdevos
Goldberg's conjectureGoldberg✭✭✭0Coloring » Edge coloringmdevos
Double-critical graph conjectureErdos; Lovasz✭✭0Coloring » Vertex coloringDFR
Shannon capacity of the seven-cycle✭✭✭0tchow
Does the chromatic symmetric function distinguish between trees?Stanley✭✭0Algebraic G.T.mdevos
Bounding the chromatic number of triangle-free graphs with fixed maximum degreeKostochka; Reed✭✭0Coloring » Vertex coloringAndrew King
Domination in plane triangulationsMatheson; Tarjan✭✭0Topological G.T.mdevos
Asymptotic Distribution of Form of Polyhedra Rüdinger✭✭0Basic G.T.andreasruedinger
Graphs with a forbidden induced tree are chi-boundedGyarfas✭✭✭0Coloring » Vertex coloringmdevos
Are vertex minor closed classes chi-bounded?Geelen✭✭0Coloring » Vertex coloringmdevos
Domination in cubic graphsReed✭✭0Basic G.T.mdevos
Crossing numbers and coloringAlbertson✭✭✭0Topological G.T. » Crossing numbersmdevos
A gold-grabbing gameRosenfeld✭✭0Graph Algorithmsmdevos
Number of Cliques in Minor-Closed ClassesWood✭✭0David Wood
Shuffle-Exchange Conjecture (graph-theoretic form)Beneš; Folklore; Stone✭✭✭0Vadim Lioubimov
Are different notions of the crossing number the same?Pach; Tóth✭✭✭0Topological G.T. » Crossing numberscibulka
Friendly partitionsDeVos✭✭0Basic G.T.mdevos
Separators in string graphsFox; Pach; Tóth✭✭0cibulka
Odd cycles and low oddness✭✭0Gagik
Stable matching in the couples problemBianco; Hartke; Larimer✭✭0tawfiq.khalil
Beneš Conjecture (graph-theoretic form)Beneš✭✭✭0Vadim Lioubimov
Approximation Ratio for Maximum Edge Disjoint Paths problemBentz✭✭0jcmeyer
Approximation ratio for k-outerplanar graphsBentz✭✭0jcmeyer
Finding k-edge-outerplanar graph embeddingsBentz✭✭0jcmeyer
Exact colorings of graphsErickson✭✭0Martin Erickson
Algorithm for graph homomorphismsFomin; Heggernes; Kratsch✭✭0Coloring » Homomorphismsjfoniok
Star chromatic index of cubic graphsDvorak; Mohar; Samal✭✭0Robert Samal
Good Edge LabelingsAraújo; Cohen; Giroire; Havet✭✭0Coloring » LabelingDOT
Covering powers of cycles with equivalence subgraphs✭0Andrew King
Matching cut and girth✭✭0w
Forcing a $K_6$-minorBarát ; Joret; Wood✭✭0Basic G.T. » MinorsDavid Wood
Circular choosability of planar graphsMohar✭0Coloring » Homomorphismsrosskang
Chromatic number of random lifts of complete graphsAmit✭✭0Probabilistic G.T.DOT
The Borodin-Kostochka ConjectureBorodin; Kostochka✭✭0Andrew King
Oriented trees in n-chromatic digraphsBurr✭✭✭0Directed Graphsfhavet
Decomposing an even tournament in directed paths.Alspach; Mason; Pullman✭✭✭0Directed Graphs » Tournamentsfhavet
Antidirected trees in digraphsAddario-Berry; Havet; Linhares Sales; Reed; Thomassé✭✭0Directed Graphsfhavet
Directed path of length twice the minimum outdegreeThomassé✭✭✭0Directed Graphsfhavet
Caccetta-Häggkvist ConjectureCaccetta; Häggkvist✭✭✭✭0Directed Graphsfhavet
Ádám's ConjectureÁdám✭✭✭0Directed Graphsfhavet
Stable set meeting all longest directed paths.Laborde; Payan; Xuong N.H.✭✭0fhavet
Splitting a digraph with minimum outdegree constraintsAlon✭✭✭0Directed Graphsfhavet

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

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

Syndicate content