List Colouring Squares of Planar Graphs

In 1977, Wegner conjectured that the chromatic number of the square of every planar graph $G$ with maximum degree $\Delta\ge8$ is at most $\lfloor\frac32 \Delta\bigr+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 c...

Full description

Bibliographic Details
Main Authors: Havet, F, Heuvel, J, McDiarmid, C, Reed, B
Format: Journal article
Language:English
Published: 2008
_version_ 1826278877610115072
author Havet, F
Heuvel, J
McDiarmid, C
Reed, B
author_facet Havet, F
Heuvel, J
McDiarmid, C
Reed, B
author_sort Havet, F
collection OXFORD
description In 1977, Wegner conjectured that the chromatic number of the square of every planar graph $G$ with maximum degree $\Delta\ge8$ is at most $\lfloor\frac32 \Delta\bigr+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.
first_indexed 2024-03-06T23:50:31Z
format Journal article
id oxford-uuid:72700038-1786-400c-867b-8aaac74ddb3c
institution University of Oxford
language English
last_indexed 2024-03-06T23:50:31Z
publishDate 2008
record_format dspace
spelling oxford-uuid:72700038-1786-400c-867b-8aaac74ddb3c2022-03-26T19:50:03ZList Colouring Squares of Planar GraphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:72700038-1786-400c-867b-8aaac74ddb3cEnglishSymplectic Elements at Oxford2008Havet, FHeuvel, JMcDiarmid, CReed, BIn 1977, Wegner conjectured that the chromatic number of the square of every planar graph $G$ with maximum degree $\Delta\ge8$ is at most $\lfloor\frac32 \Delta\bigr+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.
spellingShingle Havet, F
Heuvel, J
McDiarmid, C
Reed, B
List Colouring Squares of Planar Graphs
title List Colouring Squares of Planar Graphs
title_full List Colouring Squares of Planar Graphs
title_fullStr List Colouring Squares of Planar Graphs
title_full_unstemmed List Colouring Squares of Planar Graphs
title_short List Colouring Squares of Planar Graphs
title_sort list colouring squares of planar graphs
work_keys_str_mv AT havetf listcolouringsquaresofplanargraphs
AT heuvelj listcolouringsquaresofplanargraphs
AT mcdiarmidc listcolouringsquaresofplanargraphs
AT reedb listcolouringsquaresofplanargraphs