Graph Theory


TitleAuthor(s)Imp.¹Rec.²sort iconTopic » SubtopicPosted by
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 subgraphs0Andrew King
Matching cut and girth✭✭0w
Forcing a $K_6$-minorBarát ; Joret; Wood✭✭0Basic G.T. » MinorsDavid Wood
Circular choosability of planar graphsMohar0Coloring » 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
Long directed cycles in diregular digraphsJackson✭✭✭0Directed Graphsfhavet
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
Melnikov's valency-variety problemMelnikov0Coloring » Vertex coloringasp
Decomposing a connected graph into paths.Gallai✭✭✭0Basic G.T. » Pathsfhavet
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
Acyclic list colouring of planar graphs.Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena✭✭✭0Coloring » 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
Hoàng-Reed ConjectureHoang; Reed✭✭✭0Directed Graphsfhavet
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
Syndicate content