Improper colouring of (random) unit disk graphs

R.J. Kang, T. Müller, J.S. Sereni

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
1 Downloads (Pure)

Abstract

For any graph G, the k-improper chromatic number ¿k(G) is the smallest number of colours used in a colouring of G such that each colour class induces a subgraph of maximum degree k. We investigate ¿k for unit disk graphs and random unit disk graphs to generalise results of McDiarmid and Reed [Colouring proximity graphs in the plane, Discrete Math. 199(1–3) (1999) 123–137], McDiarmid [Random channel assignment in the plane, Random Structures Algorithms 22(2) (2003) 187–212], and McDiarmid and Müller [On the chromatic number of random geometric graphs, submitted for publication].
Original languageEnglish
Pages (from-to)1438-1454
JournalDiscrete Mathematics
Volume308
Issue number8
DOIs
Publication statusPublished - 2008

Fingerprint Dive into the research topics of 'Improper colouring of (random) unit disk graphs'. Together they form a unique fingerprint.

Cite this