Colouring triangle-free intersection graphs of boxes on the plane

A. V. Kostochka, I. G. Perepelitsa

Research output: Contribution to journalArticle

Abstract

We prove that intersection graphs of boxes on the plane with girth 6 and 8 are 3-and 2-degenerate, respectively. This implies that these graphs are 4-and 3-list-colourable, respectively.

Original languageEnglish (US)
Pages (from-to)243-249
Number of pages7
JournalDiscrete Mathematics
Volume220
Issue number1-3
DOIs
StatePublished - Jun 6 2000
Externally publishedYes

Keywords

  • Colouring
  • Intersection graphs
  • Maximum average degree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Colouring triangle-free intersection graphs of boxes on the plane'. Together they form a unique fingerprint.

  • Cite this