The strong chromatic number of a graph

Research output: Contribution to journalArticle

47 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1-7
Number of pages7
JournalRandom Structures & Algorithms
Volume3
Issue number1
DOIs
StatePublished - 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The strong chromatic number of a graph'. Together they form a unique fingerprint.

  • Cite this