179 problems

Let $f_r(n)$ be maximal such that, if a graph $G$ has the property that every subgraph $H$ on $m$ vertices is the union of a graph with chromatic number $r$ and a graph with…

Let $G$ be a $K_4$-free graph with chromatic number $4$. Must $G$ contain an odd cycle with at least two diagonals? More generally, is there some $f(r)\to \infty$ such that every g…

Let $f(m)$ be some function such that $f(m)\to \infty$ as $m\to \infty$. Does there exist a graph $G$ of infinite chromatic number such that every subgraph on $m$ vertices contains…

For a finite triple system $S$, consider triple systems that omit $S$ 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 $>\aleph_0$.

We say that a graph is $4$-chromatic critical if it has chromatic number $4$, and removing any edge decreases the chromatic number to $3$. Is there, for arbitrarily large $n$, a…

Let $A\subset\mathbb{R}^2$ 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 $A$, where two…

Let $G$ be a graph with chromatic cardinal $\aleph_1$. Is there an edge-coloring of $G$ using exactly $\aleph_1$ colors such that, for every vertex-coloring using at most countably…

Let $\kappa$ be an uncountable cardinal, i.e. $\aleph_0<\kappa$. Must there exist a cardinal $\mu$ such that every graph $G$ with chromatic cardinal $\mu$ contains a subgraph $H$ t…

For $G\sim G(n,1/2)$, can $\chi(G)$ be concentrated with high probability on a bounded number of values? More strongly, is there a function $\omega(n)\to\infty$ such that for every…

Let $f(n)$ be the maximum possible chromatic number of a triangle-free graph on $n$ vertices. Estimate $f(n)$.

Does every graph with chromatic number $\aleph_1$ contain a countable subgraph which is infinitely vertex-connected?

A critical vertex, edge, or set of edges, is one whose deletion lowers the chromatic number. Let $k\geq 4$ and $r\geq 1$. Must there exist a graph $G$ with chromatic number $k$ suc…

For every set $V$ and every $n\in\mathbb{N}$, there exists $k\in\mathbb{N}$ such that every simple graph $G$ on $V$ with chromatic number at least $k$ contains a subgraph $H$ of…

Let $k≥0$. If every finite induced subgraph $H$ of a graph $G$ has an independent set of size at least $(|V(H)|-k)/2$, must $χ(G)≤k+2$?

For $k≥4$, let $f_k(n)$ be the largest possible odd girth of a $k$-chromatic graph on $n$ vertices. Is $f_k(n)$ bounded above and below by positive constants times $n^{1/(k-2)}$?

Let $f_k(n)$ be the maximum possible chromatic number of a graph with $n$ vertices which contains no $K_k$. Is it true that, for $k\geq 4$,…

Is there a graph $G$ with vertex set $\omega_2^2$ and chromatic number $\aleph_2$ such that every subgraph whose vertices have a lesser type has chromatic number $\leq \aleph_0$? W…

Is there a graph with $\aleph_2$ vertices and chromatic number $\aleph_2$ such that every subgraph on $\aleph_1$ vertices has chromatic number $\leq\aleph_0$? Is there a graph with…

Let $k\geq 4$ and $f_k(n)$ be the largest number of edges in a graph on $n$ vertices which has chromatic number $k$ and is critical (i.e. deleting any edge reduces the chromatic nu…

Take $n$ vertex-disjoint triangles and add a Hamiltonian cycle through their $3n$ vertices using none of the triangle edges. Is the resulting graph always 3-colourable?

Let $r\geq 2$ and $G$ be a $r$-uniform hypergraph with chromatic number $3$ (that is, there is a $3$-colouring of the vertices of $G$ such that no edge is monochromatic). Suppose a…

Is there a constant $c>0$ such that every three-chromatic set system whose members all have size at least $t$ has an element belonging to at least $(1+c)^t$ members?

For fixed $r\geq3$ and all sufficiently large $k$, must every $r$-uniform hypergraph of chromatic number $k$ have at least $\binom{(r-1)(k-1)+1}{r}$ edges, with equality only for t…

Is the list chromatic number $\chi_L(G)=o(n)$ for almost every graph $G$ on $n$ vertices?