Determining the Chromatic Number of a Graph.

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1976
Accession Number
ADA035350

Entities

People

  • Colin Mcdiarmid

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Binomials
  • Computer Science
  • Computers
  • Inequalities
  • Mathematics
  • Numbers
  • Probability
  • Probability Distributions
  • Random Variables
  • Real Numbers
  • Security
  • Sequences
  • Trees (Data Structures)
  • United States
  • United States Government
  • Universities

Fields of Study

  • Mathematics

Readers

  • Neural Network Machine Learning.
  • Operations Research