List colouring squares of planar graphs - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2008

## List colouring squares of planar graphs

Frédéric Havet
Jan van den Heuvel
• Function : Author
Colin Mcdiarmid
• Function : Author
Bruce Reed

#### Abstract

In 1977, Wegner conjectured that the chromatic number of the square of every planar graph~$G$ with maximum degree $\Delta\ge8$ is at most $\bigl\lfloor\frac32\,\Delta\bigr\rfloor+1$. We show that it is at most $\frac32\,\Delta\,(1+o(1))$, and indeed this is true for the list chromatic number and for more general classes of graphs.

#### Domains

Computer Science [cs] Discrete Mathematics [cs.DM]

### Dates and versions

inria-00303303 , version 1 (21-07-2008)

### Identifiers

• HAL Id : inria-00303303 , version 1

### Cite

Frédéric Havet, Jan van den Heuvel, Colin Mcdiarmid, Bruce Reed. List colouring squares of planar graphs. [Research Report] RR-6586, INRIA. 2008. ⟨inria-00303303⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

190 View