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
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom