Premium
Generalized chromatic numbers of random graphs
Author(s) -
Bollobás Béla,
Thomason Andrew
Publication year - 1995
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.3240060222
Subject(s) - combinatorics , mathematics , chromatic scale , windmill graph , discrete mathematics , graph , friendship graph , critical graph , partition (number theory) , vertex (graph theory) , property (philosophy) , graph power , line graph , philosophy , epistemology
Abstract Let p be a hereditary graph property. The p ‐chromatic number of a graph is the minimal number of classes in a vertex partition wherein each class spans a subgraph with property p. For the property p of edgeless graphs the p ‐chromatic number is just the usual chromatic number, whose value is known to be (1/2 + o(1)) n /log 2 n for almost every graph of order n. We show that we may associate with every nontrivial hereditary property p an explicitly defined natural number r = r ( p ), and that the p ‐chromatic number is then (l/2r + o (1)) n /log 2 n for almost every graph of order n. © 1995 John Wiley & Sons, Inc.