26 problems

Plummer–Zha conjecture. Every pentagraph is $3$-colorable.

Robertson's conjecture. The Petersen graph is the only non-bipartite pentagraph that is $3$-connected and internally $4$-connected.

A graph is 4-holed if every hole in it has length $4$, where a hole is an induced cycle of length at least four. For a graph $G$, let $4chi(G)4$ denote its chromatic number and…

For an integer $\ell\geq 4$, call a graph $\ell$-holed if all holes in the graph have length $\ell$. Let $G$ be a 5-holed graph, and write $\chi(G)$ and $\omega(G)$ for its chromat…

Let $X_n$ be the unitary Cayley graph considered in the paper, and let $m(r)$ denote the maximum length of an induced cycle in $X_n$ when the underlying modulus has $r$ distinct pr…

Sivaraman's conjecture. Every short-holed graph satisfies

For any integer $t$ and any odd integer $k$, let $\mathcal{G}_{t,k}$ be the class of graphs that are $P_t$-free and whose induced odd cycles all have length $k$. Polynomial-time 3-…

Two induced cycles conjecture. There exists a function $f:\mathbb{N}^2\rightarrow\mathbb{N}$ such that every $K_{1,d}$-free graph $G$ with…

Wu–Xu–Xu conjecture. Every graph in

Let $G$ be a graph and $S\subseteq V(G)$. An $S$-cycle is a cycle containing a vertex of $S$, and an induced packing is a collection of cycles with no edge between distinct cycles.…

For a graph $G$, an induced packing of cycles is a collection of cycles with no edge between distinct cycles. For a vertex set $X$, let $B_G(X,1)$ be its closed distance-one neighb…

An induced packing of cycles is a collection of cycles such that no edge joins distinct cycles. A graph class has no induced packing of $k$ cycles if no graph in the class contains…

Hong–Kang–Yu conjecture. There exists a smallest positive integer $g(k,l)$ such that, for every $g(k,l)$-connected graph $G$, every edge $e otin E(G[X])$ with $X e V(G)$ and…

3-colorability conjecture for ${\cal G}_l$. Every graph $G\in \bigcup_{l\ge 2}{\cal G}_l$ satisfies $\chi(G)\le 3$.

For each $\ell\geq 3$, let $C_\ell$ be the cycle of length $\ell$. A hole is an induced cycle of length at least $4$, and a graph is $C_4$-free if it contains no $C_4$. Let…

Let $C_4$ denote the cycle of length $4$. A hole is an induced cycle of length at least $4$, and a graph is $C_4$-free if it contains no cycle of length $4$. For a graph $G$ and…

For an integer $k$, an induced cycle with a $k$-neighbour vertex is an induced cycle having some vertex with at least $k$ neighbours on the cycle. High-cycle-degree conjecture. For…

For an integer $k$, a cycle with exactly $k$ chords is a cycle together with exactly $k$ additional edges joining nonconsecutive cycle vertices. Exact-chord conjecture. For every…

A set $A$ of integers is constricting if the ideal of graphs with no hole whose length belongs to $A$ is $χ$-bounded. Density-zero constricting-set conjecture. There exists a set…

A set $S$ of integers is constricting if the ideal of graphs containing no hole with length in $S$ is $χ$-bounded. Positive-lower-density conjecture. A set of integers is constrict…

A set $S$ of integers is constricting if the ideal of graphs containing no hole with length in $S$ is $χ$-bounded. Bounded-gap constricting-set conjecture. Every infinite set $S$ o…

Conjecture on consecutive holes. Every graph with huge chromatic number and bounded clique number contains $k$ holes with consecutive lengths.

Let $G$ be a graph, and let $\kappa$ and $\ell$ be nonnegative integers. A hole is an induced cycle. Conjecture on consecutive hole lengths outside large cliques. There exists…

Let $c\in(0,1)$, let $l(n)=\lceil cn\rceil$, and let $c(n,l)$ be the maximum number of induced cycles of length $l$ in a graph on $n$ vertices. Let $C(n,l)$ be the set of graphs at…

Cubic induced-cycle bound conjecture.