11 problems

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-…

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…

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…

Five-holed graph chromatic bound conjecture. If $G$ is $5$-holed, then

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…

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…

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…

Kalai–Meshulam chromatic conjecture. A graph with high enough chromatic number has an induced cycle of length divisible by three.

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…

Vertex-prescribed induced-cycle conjecture. For every $k$, there exists an $h(k)$ such that for every vertex $v$ of every $h(k)$-connected graph $G$, there exists an induced cycle…