13 problems

For $n\ge t$, let $T_{n,t}$ be the $n$-vertex complete $t$-partite Turán graph whose part sizes differ by at most one. For a graph $G$, a $t$-clique cover is a collection of clique…

For a graph $G$, let $\mathcal{C}\mathcal{C}_t(G)$ and $\mathcal{C}\mathcal{C}^*_t(G)$ denote its integral and fractional $t$-clique cover numbers, respectively. Additive-gap conje…

Hajebi's conjecture. For every integer $t\ge 1$, there exists $\varepsilon>0$ such that every $K_{t,t}$-free graph $G$ has a clique cover of size

Erdős–Goodman–Pósa conjecture. If

Let $H$ be a realizable graph. A clique cover of $H$ is a collection of cliques whose union covers all edges of $H$, and let $n$ be the smallest number of cliques in such a cover.…

Let $G$ be a simple graph on $n$ vertices with $m$ edges. Write $\theta(G)$ for its minimum clique-cover size, and define … Set $\overline{x}=\lfloor x^2/4\rfloor$. The exact upper…

Shallow-minor star conjecture. If $G$ does not have an induced star on $s$ leaves, then, for every $t\ge 0$,

Let $G$ be sampled from the binomial random graph model ${\mathcal G}(n,p)$, where $p$ is a constant with $0<p<1$. Let $\theta'_0(G)$ be the minimum, over all clique covers of $G$,…

Zaare-Nahandi's conjecture. $G$ is semi-perfect.

Let $G$ be a graph on $n$ vertices, and let $\alpha(G)$ denote its independence number, the maximum size of a set of pairwise nonadjacent vertices. The graph is triad-free when…

Sigma clique covering growth conjecture. For every positive integers $t$ and $d$, if $t\geq f(d)$, then

Sigma clique covering sharpness conjecture. This upper bound is best up to a constant factor for large enough $n$.

Let $g$ be the almost identity function … For a graph $G$, let $\alpha(G)$ be its independence number and let $\theta(G)$ be its minimum clique-cover number. The complementary boun…