Home » Subject

Graph Theory


TitleAuthor(s)Imp.¹sort iconRec.²Topic » SubtopicPosted by
4-regular 4-chromatic graphs of high girthGrunbaum✭✭0Coloringmdevos
Negative association in uniform forestsPemantle✭✭0Probabilistic G.T.mdevos
Counting 3-colorings of the hex latticeThomassen✭✭0Coloring » Vertex coloringmdevos
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
Double-critical graph conjectureErdos; Lovasz✭✭0Coloring » Vertex coloringDFR
Book Thickness of SubdivisionsBlankenship; Oporowski✭✭1David Wood
3-Colourability of Arrangements of Great CirclesFelsner; Hurtado; Noy; Streinu✭✭1Topological G.T. » ColoringDavid Wood
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
Are vertex minor closed classes chi-bounded?Geelen✭✭0Coloring » Vertex coloringmdevos
Domination in cubic graphsReed✭✭0Basic G.T.mdevos
A gold-grabbing gameRosenfeld✭✭0Graph Algorithmsmdevos
Number of Cliques in Minor-Closed ClassesWood✭✭0David Wood
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
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
Star chromatic index of complete graphsDvorak; Mohar; Samal✭✭1Robert Samal
Extremal problem on the number of tree endomorphismZhicong Lin✭✭1Extremal G.T.shudeshijie
Good Edge LabelingsAraújo; Cohen; Giroire; Havet✭✭0Coloring » LabelingDOT
Matching cut and girth✭✭0w
Forcing a $K_6$-minorBarát ; Joret; Wood✭✭0Basic G.T. » MinorsDavid Wood
Minimal graphs with a prescribed number of spanning treesAzarija; Skrekovski✭✭1azi
Chromatic number of random lifts of complete graphsAmit✭✭0Probabilistic G.T.DOT
The Borodin-Kostochka ConjectureBorodin; Kostochka✭✭0Andrew King
Choice Number of k-Chromatic Graphs of Bounded OrderNoel✭✭1Coloring » Vertex coloringjnoel12
Antidirected trees in digraphsAddario-Berry; Havet; Linhares Sales; Reed; Thomassé✭✭0Directed Graphsfhavet
Stable set meeting all longest directed paths.Laborde; Payan; Xuong N.H.✭✭0fhavet
Strong edge colouring conjectureErdos; Nesetril✭✭0Coloring » Edge coloringfhavet
Arc-disjoint out-branching and in-branchingThomassen✭✭0Directed Graphsfhavet
Arc-disjoint strongly connected spanning subdigraphsBang-Jensen; Yeo✭✭0fhavet
Coloring the union of degenerate graphsTarsi✭✭0Coloringfhavet
Do any three longest paths in a connected graph have a vertex in common? Gallai✭✭0fhavet
Decomposing an eulerian graph into cycles.Hajós✭✭0Basic G.T. » Cyclesfhavet
Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour.Sabidussi✭✭0Basic G.T. » Cyclesfhavet
Partition of a cubic 3-connected graphs into paths of length 2.Kelmans✭✭0Basic G.T. » Pathsfhavet
Lovász Path Removal ConjectureLovasz✭✭0fhavet

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

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

Syndicate content