chromatic number


Cycles in Graphs of Large Chromatic Number ★★

Author(s): Brewster; McGuinness; Moore; Noel

\begin{conjecture} If $\chi(G)>k$, then $G$ contains at least $\frac{(k+1)(k-1)!}{2}$ cycles of length $0\bmod k$. \end{conjecture}

Keywords: chromatic number; cycles

Erdős–Faber–Lovász conjecture ★★★

Author(s): Erdos; Faber; Lovasz

\begin{conjecture} If $G$ is a simple graph which is the union of $k$ pairwise edge-disjoint complete graphs, each of which has $k$ vertices, then the chromatic number of $G$ is $k$. \end{conjecture}

Keywords: chromatic number

Choosability of Graph Powers ★★

Author(s): Noel

\begin{question}[Noel, 2013] Does there exist a function $f(k)=o(k^2)$ such that for every graph $G$, \[\text{ch}\left(G^2\right)\leq f\left(\chi\left(G^2\right)\right)?\] \end{question}

Keywords: choosability; chromatic number; list coloring; square of a graph

Ohba's Conjecture ★★

Author(s): Ohba

\begin{conjecture} If $|V(G)|\leq 2\chi(G)+1$, then $\chi_\ell(G)=\chi(G)$. \end{conjecture}

Keywords: choosability; chromatic number; complete multipartite graph; list coloring

Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

\begin{conjecture} A triangle-free graph with maximum degree $\Delta$ has chromatic number at most $\ceil{\frac{\Delta}{2}}+2$. % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords: chromatic number; girth; maximum degree; triangle free

Syndicate content