Colouring triangle-free intersection graphs of boxes on the plane

A. V. Kostochka; I. G. Perepelitsa

doi:10.1016/S0012-365X(00)00027-3

Colouring triangle-free intersection graphs of boxes on the plane

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	243-249
Number of pages	7
Journal	Discrete Mathematics
Volume	220
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(00)00027-3
State	Published - Jun 6 2000
Externally published	Yes

Keywords

Colouring
Intersection graphs
Maximum average degree

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/S0012-365X(00)00027-3

Library availability

Discover UIUC Full Text

Cite this

@article{d9c53096476844588dbe58e8a355cdad,

title = "Colouring triangle-free intersection graphs of boxes on the plane",

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.",

keywords = "Colouring, Intersection graphs, Maximum average degree",

author = "Kostochka, {A. V.} and Perepelitsa, {I. G.}",

note = "Funding Information: ∗Corresponding author. 1Partially supported by the grant 96-01-01614 of the Russian Foundation for Fundamental Research. 2Partially supported by the grant 97-01-01075 of the Russian Foundation for Fundamental Research.",

year = "2000",

month = jun,

day = "6",

doi = "10.1016/S0012-365X(00)00027-3",

language = "English (US)",

volume = "220",

pages = "243--249",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Colouring triangle-free intersection graphs of boxes on the plane

AU - Kostochka, A. V.

AU - Perepelitsa, I. G.

N1 - Funding Information: ∗Corresponding author. 1Partially supported by the grant 96-01-01614 of the Russian Foundation for Fundamental Research. 2Partially supported by the grant 97-01-01075 of the Russian Foundation for Fundamental Research.

PY - 2000/6/6

Y1 - 2000/6/6

N2 - 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.

AB - 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.

KW - Colouring

KW - Intersection graphs

KW - Maximum average degree

UR - http://www.scopus.com/inward/record.url?scp=0347016232&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347016232&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(00)00027-3

DO - 10.1016/S0012-365X(00)00027-3

M3 - Article

AN - SCOPUS:0347016232

SN - 0012-365X

VL - 220

SP - 243

EP - 249

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Colouring triangle-free intersection graphs of boxes on the plane

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this