235 problems
Let be an orientation of a complete multipartite graph, and let be the number of its parts having odd size. Write for the Eulerian polynomial of , and let…
For every positive integer and every finite -regular digraph , let be the maximum cardinality of a collection of directed cycles in that all contain a common v…
For every positive integer and every finite digraph , if is -strongly connected and , where is the maximum cardina…
For every integer , every -strong digraph has a spanning subdigraph such that is oriented and -strong; equivalently, , ,…
For all positive integers and , every digraph on vertices with more than arcs contains every antidirected tree with arcs as a subdigraph. Here, an a…
Given a digraph , determine whether there is a partition such that one of the following holds: (i) is a perfect matching and …
For each fixed integer , determine the largest function such that, for every sufficiently large integer and every digraph with arcs and minimum semideg…
vertex-disjoint directed cycles in su…
Let . A digraph has girth at least if its shortest directed cycle has length at least , and let denote its minimum out-degree. Caccetta–…
A graph is -connected if it remains connected after the deletion of any set of at most vertices. An orientation of is -strong if its corresponding digraph…
Let be a source-free bipartite digraph, meaning that every vertex has a nonempty set of external in-neighbors. A quasikernel of is an independent set such…
Let be a finite simple digraph, and let be the minimum integer such that every digraph with minimum outdegree at least contains vertex-disjoint directed cycle…
Thomassen's conjecture. There exists an integer such that every -arc-strong digraph has a good -pair for every choice of .
Let be an acyclic digraph, and let denote the minimum out-degree of a digraph . A subdivision of is obtained by replacing the arcs of by directed paths…
Magnant–Martin's strengthened conjecture. If is a -regular digraph on vertices, then
Erdős–Neumann-Lara conjecture. For every integer there is an integer such that, for every graph , implies .
Behzad–Chartrand–Wall conjecture. Every -vertex oriented digraph with minimum out-degree and minimum in-degree at least contains a directed triangle.
Bang-Jensen and Yeo's conjecture. There exists an integer such that every -arc-strong digraph has a strong arc decomposition.
Let be the minimum number of arcs in a -dicritical digraph of order , and let be the minimum number of arcs in a -dicritical oriented graph of order ,…
Bang-Jensen–Yeo's conjecture. There exists an integer such that every -arc-strong digraph has an arc-partition
Let be a digraph. A majority colouring of is a vertex colouring such that at least half of the out-neighbours of every vertex have a colour different from . K…
Linial's conjecture. For every digraph and every positive integer ,
Linear-connectivity partition conjecture. There exists a constant such that the vertices of every strongly -connected digraph with can be…
Let be a digraph. A stable set is a set of pairwise non-adjacent vertices, and a path partition is a collection of disjoint paths containing every vertex of exactly once. A…
McDiarmid–Mohar conjecture. Every oriented graph satisfies