chromatic number

Graph Theory » Coloring » Vertex coloring

Cycles in Graphs of Large Chromatic Number ★★

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

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

Keywords: chromatic number; cycles

Posted by Jon Noel
updated September 20th, 2015

add new comment

Graph Theory » Coloring » Vertex coloring

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

Author(s): Erdos; Faber; Lovasz

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$ .

Keywords: chromatic number

Posted by Jon Noel
updated August 22nd, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Choosability of Graph Powers ★★

Author(s): Noel

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)?$