5 problems

Let $\mathcal{G}$ be a graph and let $k\geq 1$. The parameter $\theta_k(\mathcal{G})$ and the strengthened generalized $\vartheta$-number $\vartheta'_k(\mathcal{G})$ are defined as…

Let $G$ be a 3-colorable planar graph. A segment representation of $G$ assigns a straight line segment in the plane to each vertex of $G$ so that two segments intersect if and only…

Let $H$ be a simple graph. In \textrm{Max Partial }H\textrm{-Coloring}\, the input is a graph $G$ with a revenue function $\mathsf{rev}:V(G)\times V(H)\to\mathbb{Q}_{\geq 0}$, an…

Let $p$ and $q$ be primes satisfying $q>p\geq 3$, and let $\mathcal{U}(\mathbb{Z}_{pq})$ denote the unitary addition Cayley graph on $\mathbb{Z}_{pq}$. Achromatic number conjecture…

Let $k\geq 4$ and $n>k+1$, and let $L_k(n)$ be the smallest integer $l$ such that every $k$-critical graph on $n$ vertices has circumference at least $l$, where a graph is $k$-crit…