Determining the Chromatic Number of a Graph.

reportActive / Technical Report | Accession Number: ADA035350 | Open PDF

Abstract:

Certain algorithms concerning coloring graphs involve the partial exploration of Zykov trees. We investigate the size of such trees, and prove that a certain class of branch-and-bound algorithms for determining the chromatic number of a graph requires in probability a number of steps which grows faster than exponentially with the number of vertices of the graph. Author

Author(s):
Mcdiarmid, Colin
Author Organization(s):
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Descriptive Note:
Technical rept.,
Pagination:
0063

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
STAN-CS-76-576
Contract/Grant Number(s):
N00014-76-C-0330, NSF-MCS-72-03752
 Subject Terms
Joint Capability Areas:
JCA_5_Command and Control; JCA_1.2_Force Preparation; JCA_1_Force Support; JCA_1.2.3_Educating
Modernization Areas:
Fully Networked C3
Communities of Interest:
C4I
Descriptor(s):
*ALGORITHMS, *GRAPHS, PROBABILITY, COMBINATORIAL ANALYSIS, CHROMATICITY, NUMBERING SYSTEMS
Field(s)/Group(s):
Statistics and Probability
Keyword(s):
Coloring graphs, Zykov trees, Combinatorial mathematics
Report Date:
1976 Oct 01