180 problems
Alon–Krivelevich–Sudakov conjecture. For every graph , there is a constant such that, whenever is an -free graph of maximum degree , one has
There exists an integer such that, for every tournament and every pair of disjoint vertex subsets with and , there ar…
Let be maximal such that, if a graph has the property that every subgraph on vertices is the union of a graph with chromatic number and a graph with…
Let be a -free graph with chromatic number . Must contain an odd cycle with at least two diagonals? More generally, is there some such that every g…
Let be some function such that as . Does there exist a graph of infinite chromatic number such that every subgraph on vertices contains…
Let be an infinite set which contains no three points on a line and no four points on a circle. Consider the graph with vertices the points in , where two…
For a finite triple system , consider triple systems that omit and have uncountable chromatic number. (a) If one exists, must one exist with cardinality at most…
Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number .
We say that a graph is -chromatic critical if it has chromatic number , and removing any edge decreases the chromatic number to . Is there, for arbitrarily large , a…
Let be a simple graph, with , and let denote its chromatic number, the least cardinality of a set admitting a proper coloring of . Assume…
For a graph , let denote its chromatic cardinal: the least cardinality of a set of colors admitting a proper coloring of the vertices of . A graph is triangle-free…
For each positive integer , let be the random graph on labelled vertices in which each possible edge is present independently with probability , and…
For each positive integer , let range over finite triangle-free graphs with exactly vertices, where triangle-free means that contains no cycle of length . Write…
Let be a graph, and let denote its chromatic number. Is it true that whenever , there is a countably infinite subgraph such that ever…
For a graph , write for its chromatic number, for the graph obtained by deleting a vertex , and for the graph obtained by deleting an edge set…
The intended question is whether, for every positive integer n, there is a positive integer k depending only on n such that every simple graph G with chromatic number at least k ha…
Let be a non-negative integer and let be a graph, not necessarily finite. For a finite set , write for the subgraph induced by , and let…
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 integers and , let be the maximum chromatic number among finite simple graphs with exactly vertices that contain no clique of order (tha…
Let be the set of pairs with , ordered lexicographically, so that its order type is the ordinal product . For a graph…
A graph here is a simple undirected graph , with , and denotes its chromatic number. A subgraph may use any subset of the edges on its vertex s…
Let and be the largest number of edges in a graph on vertices which has chromatic number and is critical (i.e. deleting any edge reduces the chromatic nu…
Let be a positive integer, let be a set of vertices, and let be pairwise vertex-disjoint triangles whose vertex sets partition . Let be a Hamil…
Let be an integer, and let be a finite -uniform hypergraph: is a family of -element subsets of , and, as in the set-family convention,…
Let be a set and let be a family of subsets of . Call -chromatic if can be partitioned into classes, none of which contai…