Home » Subject

Graph Theory


TitleAuthor(s)Imp.¹sort iconRec.²Topic » SubtopicPosted by
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
Large induced forest in a planar graph.Abertson; Berman✭✭0Topological G.T.fhavet
Subdivision of a transitive tournament in digraphs with large outdegree. Mader✭✭0Directed Graphsfhavet
Turán number of a finite family.Erdos; Simonovits✭✭0fhavet
Subgraph of large average degree and large girth.Thomassen✭✭0Basic G.T.fhavet
Complexity of the H-factor problem.Kühn; Osthus✭✭0Extremal G.T.fhavet
Simultaneous partition of hypergraphsKühn; Osthus✭✭0Hypergraphsfhavet
Odd-cycle transversal in triangle-free graphsErdos; Faudree; Pach; Spencer✭✭0Extremal G.T.fhavet
Triangle-packing vs triangle edge-transversal.Tuza✭✭0Extremal G.T.fhavet
Earth-Moon ProblemRingel✭✭1Coloring » Vertex coloringfhavet
Every 4-connected toroidal graph has a Hamilton cycleGrunbaum; Nash-Williams✭✭0Topological G.T.fhavet
Switching reconstruction conjectureStanley✭✭0fhavet
Switching reconstruction of digraphsBondy; Mercier✭✭0fhavet
Hamilton cycle in small d-diregular graphsJackson✭✭0Directed Graphsfhavet
Edge-disjoint Hamilton cycles in highly strongly connected tournaments.Thomassen✭✭0Directed Graphs » Tournamentsfhavet
Every prism over a 3-connected planar graph is hamiltonian.Kaiser; Král; Rosenfeld; Ryjácek; Voss✭✭0Basic G.T. » Cyclesfhavet
4-connected graphs are not uniquely hamiltonianFleischner✭✭0Basic G.T. » Cyclesfhavet
Turán's problem for hypergraphsTuran✭✭0Hypergraphsfhavet
Hamilton decomposition of prisms over 3-connected cubic planar graphsAlspach; Rosenfeld✭✭0Basic G.T. » Cyclesfhavet
List chromatic number and maximum degree of bipartite graphsAlon✭✭0Coloring » Vertex coloringfhavet
Colouring the square of a planar graphWegner✭✭0Coloring » Vertex coloringfhavet
Weighted colouring of hexagonal graphs.McDiarmid; Reed✭✭0Coloring » Vertex coloringfhavet

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

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

Syndicate content