Acyclic colouring of 1-planar graphs

O. V. Borodin; A. V. Kostochka; A. Raspaud; E. Sopena

doi:10.1016/S0166-218X(00)00359-0

Acyclic colouring of 1-planar graphs

O. V. Borodin, A. V. Kostochka, A. Raspaud, E. Sopena

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

Abstract

A graph is 1-planar if it can be drawn on the plane in such a way that every edge crosses at most one other edge. We prove that the acyclic chromatic number of every 1-planar graph is at most 20.

Original language	English (US)
Pages (from-to)	29-41
Number of pages	13
Journal	Discrete Applied Mathematics
Volume	114
Issue number	1-3
DOIs	https://doi.org/10.1016/S0166-218X(00)00359-0
State	Published - Oct 30 2001
Externally published	Yes

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Online availability

10.1016/S0166-218X(00)00359-0

Library availability

Discover UIUC Full Text

Cite this

@article{575b8fda6a774e088d5c5913edc598c6,

title = "Acyclic colouring of 1-planar graphs",

abstract = "A graph is 1-planar if it can be drawn on the plane in such a way that every edge crosses at most one other edge. We prove that the acyclic chromatic number of every 1-planar graph is at most 20.",

author = "Borodin, {O. V.} and Kostochka, {A. V.} and A. Raspaud and E. Sopena",

year = "2001",

month = oct,

day = "30",

doi = "10.1016/S0166-218X(00)00359-0",

language = "English (US)",

volume = "114",

pages = "29--41",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Acyclic colouring of 1-planar graphs

AU - Borodin, O. V.

AU - Kostochka, A. V.

AU - Raspaud, A.

AU - Sopena, E.

PY - 2001/10/30

Y1 - 2001/10/30

N2 - A graph is 1-planar if it can be drawn on the plane in such a way that every edge crosses at most one other edge. We prove that the acyclic chromatic number of every 1-planar graph is at most 20.

AB - A graph is 1-planar if it can be drawn on the plane in such a way that every edge crosses at most one other edge. We prove that the acyclic chromatic number of every 1-planar graph is at most 20.

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

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

U2 - 10.1016/S0166-218X(00)00359-0

DO - 10.1016/S0166-218X(00)00359-0

M3 - Article

AN - SCOPUS:0035975885

SN - 0166-218X

VL - 114

SP - 29

EP - 41

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

Acyclic colouring of 1-planar graphs

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this