The strong chromatic number of a graph

Noga Alon

doi:10.1002/rsa.3240030102

The strong chromatic number of a graph

Noga Alon

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

57 Scopus citations

Abstract

It is shown that there is an absolute constant c with the following property: For any two graphs G₁ = (V, E₁) and G₂ = (V, E₂) on the same set of vertices, where G₁ has maximum degree at most d and G₂ is a vertex disjoint union of cliques of size cd each, the chromatic number of the graph G = (V, E₁ U E₂) is precisely cd. The proof is based on probabilistic arguments.

Original language	English (US)
Pages (from-to)	1-7
Number of pages	7
Journal	Random Structures & Algorithms
Volume	3
Issue number	1
DOIs	https://doi.org/10.1002/rsa.3240030102
State	Published - 1992
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Access to Document

10.1002/rsa.3240030102

Cite this

@article{a644b0a22160477e9fb62bad31c6f4ed,

title = "The strong chromatic number of a graph",

abstract = "It is shown that there is an absolute constant c with the following property: For any two graphs G1 = (V, E1) and G2 = (V, E2) on the same set of vertices, where G1 has maximum degree at most d and G2 is a vertex disjoint union of cliques of size cd each, the chromatic number of the graph G = (V, E1 U E2) is precisely cd. The proof is based on probabilistic arguments.",

author = "Noga Alon",

year = "1992",

doi = "10.1002/rsa.3240030102",

language = "English (US)",

volume = "3",

pages = "1--7",

journal = "Random Structures & Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "1",

}

TY - JOUR

T1 - The strong chromatic number of a graph

AU - Alon, Noga

PY - 1992

Y1 - 1992

N2 - It is shown that there is an absolute constant c with the following property: For any two graphs G1 = (V, E1) and G2 = (V, E2) on the same set of vertices, where G1 has maximum degree at most d and G2 is a vertex disjoint union of cliques of size cd each, the chromatic number of the graph G = (V, E1 U E2) is precisely cd. The proof is based on probabilistic arguments.

AB - It is shown that there is an absolute constant c with the following property: For any two graphs G1 = (V, E1) and G2 = (V, E2) on the same set of vertices, where G1 has maximum degree at most d and G2 is a vertex disjoint union of cliques of size cd each, the chromatic number of the graph G = (V, E1 U E2) is precisely cd. The proof is based on probabilistic arguments.

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

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

U2 - 10.1002/rsa.3240030102

DO - 10.1002/rsa.3240030102

M3 - Article

AN - SCOPUS:84990648282

SN - 1042-9832

VL - 3

SP - 1

EP - 7

JO - Random Structures & Algorithms

JF - Random Structures & Algorithms

IS - 1

ER -

The strong chromatic number of a graph

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this