Premium
The strong chromatic number of a graph
Author(s) -
Alon Noga
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030102
Subject(s) - combinatorics , chromatic scale , mathematics , graph , vertex (graph theory) , disjoint sets , discrete mathematics , constant (computer programming) , bound graph , graph power , computer science , line graph , programming language
Abstract It is shown that there is an absolute constant c with the following property: For any two graphs G 1 = ( V, E 1 ) and G 2 = ( V, E 2 ) on the same set of vertices, where G 1 has maximum degree at most d and G 2 is a vertex disjoint union of cliques of size cd each, the chromatic number of the graph G = ( V, E 1 U E 2 ) is precisely cd . The proof is based on probabilistic arguments.