# chromatic number

## Cycles in Graphs of Large Chromatic Number ★★

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

**Conjecture**If , then contains at least cycles of length .

Keywords: chromatic number; cycles

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

Author(s): Erdos; Faber; Lovasz

**Conjecture**If is a simple graph which is the union of pairwise edge-disjoint complete graphs, each of which has vertices, then the chromatic number of is .

Keywords: chromatic number

## Choosability of Graph Powers ★★

Author(s): Noel

**Question (Noel, 2013)**Does there exist a function such that for every graph ,

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

## Ohba's Conjecture ★★

Author(s): Ohba

**Conjecture**If , then .

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

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

**Conjecture**A triangle-free graph with maximum degree has chromatic number at most .

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