The chromatic number of graph powers

Noga Alon; Bojan Mohar

doi:10.1017/S0963548301004965

The chromatic number of graph powers

Noga Alon, Bojan Mohar

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

42 Scopus citations

Abstract

It is shown that the maximum possible chromatic number of the square of a graph with maximum degree d and girth g is (1 + o(1))d² if g = 3, 4, 5 or 6, and is Θ(d²/log d) if g ≥ 7. Extensions to higher powers are considered as well.

Original language	English (US)
Pages (from-to)	1-10
Number of pages	10
Journal	Combinatorics Probability and Computing
Volume	11
Issue number	1
DOIs	https://doi.org/10.1017/S0963548301004965
State	Published - Jan 2002
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1017/S0963548301004965

Cite this

@article{2d9441881b824a04821abf40257eec51,

title = "The chromatic number of graph powers",

abstract = "It is shown that the maximum possible chromatic number of the square of a graph with maximum degree d and girth g is (1 + o(1))d2 if g = 3, 4, 5 or 6, and is Θ(d2/log d) if g ≥ 7. Extensions to higher powers are considered as well.",

author = "Noga Alon and Bojan Mohar",

year = "2002",

month = jan,

doi = "10.1017/S0963548301004965",

language = "English (US)",

volume = "11",

pages = "1--10",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "1",

}

TY - JOUR

T1 - The chromatic number of graph powers

AU - Alon, Noga

AU - Mohar, Bojan

PY - 2002/1

Y1 - 2002/1

N2 - It is shown that the maximum possible chromatic number of the square of a graph with maximum degree d and girth g is (1 + o(1))d2 if g = 3, 4, 5 or 6, and is Θ(d2/log d) if g ≥ 7. Extensions to higher powers are considered as well.

AB - It is shown that the maximum possible chromatic number of the square of a graph with maximum degree d and girth g is (1 + o(1))d2 if g = 3, 4, 5 or 6, and is Θ(d2/log d) if g ≥ 7. Extensions to higher powers are considered as well.

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

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

U2 - 10.1017/S0963548301004965

DO - 10.1017/S0963548301004965

M3 - Article

AN - SCOPUS:0036003893

SN - 0963-5483

VL - 11

SP - 1

EP - 10

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 1

ER -

The chromatic number of graph powers

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this