Coloring Graphs with Sparse Neighborhoods

Noga Alon; Michael Krivelevich; Benny Sudakov

doi:10.1006/jctb.1999.1910

Coloring Graphs with Sparse Neighborhoods

Noga Alon, Michael Krivelevich, Benny Sudakov

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

79 Scopus citations

Abstract

It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d²/f is at most O(d/logf). This is tight (up to a constant factor) for all admissible values of d and f.

Original language	English (US)
Pages (from-to)	73-82
Number of pages	10
Journal	Journal of Combinatorial Theory. Series B
Volume	77
Issue number	1
DOIs	https://doi.org/10.1006/jctb.1999.1910
State	Published - Sep 1999
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1999.1910

Cite this

@article{c088c9407c0c45bcbba99541b130a0e6,

title = "Coloring Graphs with Sparse Neighborhoods",

abstract = "It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d2/f is at most O(d/logf). This is tight (up to a constant factor) for all admissible values of d and f.",

author = "Noga Alon and Michael Krivelevich and Benny Sudakov",

note = "Funding Information: * Research supported in part by a U.S.A. Israeli BSF grant, by a grant from the Israel Science Foundation, and by a state of New Jersey grant. -Research supported by an IAS DIMACS Postdoctoral Fellowship. Part of this research was done during a visit at the IAS, Princeton, NJ.",

year = "1999",

month = sep,

doi = "10.1006/jctb.1999.1910",

language = "English (US)",

volume = "77",

pages = "73--82",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Coloring Graphs with Sparse Neighborhoods

AU - Alon, Noga

AU - Krivelevich, Michael

AU - Sudakov, Benny

N1 - Funding Information: * Research supported in part by a U.S.A. Israeli BSF grant, by a grant from the Israel Science Foundation, and by a state of New Jersey grant. -Research supported by an IAS DIMACS Postdoctoral Fellowship. Part of this research was done during a visit at the IAS, Princeton, NJ.

PY - 1999/9

Y1 - 1999/9

N2 - It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d2/f is at most O(d/logf). This is tight (up to a constant factor) for all admissible values of d and f.

AB - It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d2/f is at most O(d/logf). This is tight (up to a constant factor) for all admissible values of d and f.

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

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

U2 - 10.1006/jctb.1999.1910

DO - 10.1006/jctb.1999.1910

M3 - Article

AN - SCOPUS:0003151866

SN - 0095-8956

VL - 77

SP - 73

EP - 82

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -

Coloring Graphs with Sparse Neighborhoods

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this