126 problems
All graphs under consideration are finite and simple. For a graph and a vertex , let denote the degree of . Dean's conjecture. For every integer , every…
Let be a graph with vertices and edges. Are there subgraphs such that - has edges and every two edges in a…
For every infinite arithmetic progression with positive common difference that contains an even number, does there exist a constant suc…
For each integer , let be the least integer for which there is a graph with vertices and edges that contains a cycle of every length from thro…
Let be a graph with girth greater than , meaning that it has no cycles of length or . An orientation of assigns a direction to every edge; it is acyclic if it…
For integers and , let be the largest integer for which there is a graph on vertices with chromatic number and every odd cycle in…
For each integer , let be a finite simple graph with and . Is there a cycle in and a vertex such that is a…
For a finite graph , let be its minimum degree, let be the length of its shortest cycle (taken to be if it has no cycles), and def…
For a positive integer , let range over finite simple graphs with . For a simple cycle in , a chord is an edge of joining two vertices of that are n…
Let be a finite graph, let denote its number of vertices, let be its chromatic number, and let be the length of its shortest cycle…
For a positive integer , let range over finite simple undirected graphs with . A cycle means a simple cycle, and two cycles are edge-disjoint if they share no edge…
For a finite graph , write . A decomposition into cycles and edges means a partition of into edge sets of cycles and single-edge pieces; in particular, all piec…
For a graph , let denote its chromatic number, and, for each integer , define … For graphs with , these minima exist: the De Bruijn–Erdős the…
For integers and , does there exist a finite integer such that every graph with chromatic number at least has an ordinary subgraph satisf…
For an integer and a graph on vertices, define its cycle set by … Let be the number of distinct sets attained by graphs on vertices. Th…
Let be a function on the positive integers with , possibly very slowly. Is there a graph of infinite chromatic number such that every finite subgraph on vert…
Does there exist a zero-density set of positive integers and a constant such that every sufficiently large graph with average degree at least contains a cycle wh…
Let be a graph with vertices and edges, and be the lengths of cycles in . Is it true that Is the sum…
Every finite simple graph with minimum degree at least contains a cycle of length for some natural number with .
Must every graph of infinite chromatic number contain cycles of length for infinitely many integers ?
Does every graph on vertices with edges contain many copies of ?
If a graph contains odd cycles of at most different lengths, must , with equality only when contains ?
If an infinite graph has infinite chromatic number and are the lengths of its odd cycles, must diverge?
A decomposition of a graph is a partition of its edge set into subgraphs of the indicated types. Erdős–Gallai conjecture. Every -vertex graph has a decomposition into cyc…
For a digraph , its minimum out-degree is the minimum number of outgoing edges over all vertices of . Lichiardopol's conjecture. For every , there exists an integer…