## Doctoral Dissertations

## Abstract

"The composite graph coloring problem (CGCP) is a generalization of the standard graph coloring problem (SGCP). Associated with each vertex is a positive integer called its chromaticity. The chromaticity of a vertex specifies the number of consecutive colors which must be assigned to it.

An exact algorithm for solving the CGCP is presented. The algorithm is a generalization of the vertex-sequential with dynamic reordering approach for the SGCP. It is shown that the method is as effective on composite graphs as its counterpart is on standard graphs. Let π³Μ
Μ
(CG_{n,p}) and π³Μ
Μ
(SG_{n,p}) denote, respectively, the mean chromatic number of a sample of random composite and standard graphs of order n and edge density p. It is demonstrated that the ratio π³Μ
Μ
(CG_{n,p}) / π³Μ
Μ
(SG_{n,p}), depends on p, but, for fixed p, is essentially constant, over the range of values of n for which the algorithms were applied.

Several new heuristic methods for efficiently approximating π³(CG_{n,p}) for large values of n are presented. Of these, the CDsatur and CDsaturI1 algorithms, which are generalizations of the well known Dsatur algorithm, are shown to be very competitive with previously tested procedures.

A known method for calculating probabilistic lower bounds for π³Μ
Μ
(SG_{n,p}) is generalized to produce such bounds for π³Μ
Μ
(CG_{n,p}). Also, a method for estimating the value of π³Μ
Μ
(SG_{n,p}), is shown to produce probabilistic upper bounds for π³Μ
Μ
(SGn,p). This procedure is then generalized to a method for calculating probabilistic upper bounds for π³Μ
Μ
(CG_{n,p}). The resulting bounds are used to evaluate the actual effectiveness of several heuristic algorithms. It is shown that, for fixed p, although the mean absolute error of the heuristic procedures appears to increase as n is varied from 100 to 1000, the mean relative error remains reasonably constant"--

Abstract, page iii.

## Advisor(s)

Gillett, Billy E.

## Committee Member(s)

Ho, C. Y. (Chung You), 1933-1988

Prater, John Bruce, 1932-2002

Rigler, A. K.

Koederitz, Leonard

## Department(s)

Computer Science

## Degree Name

Ph. D. in Computer Science

## Publisher

University of Missouri--Rolla

## Publication Date

Fall 1990

## Pagination

xv, 373 pages

## Note about bibliography

Includes bibliographical references (pages 370-372).

## Rights

Β© 1990 Jack L. Oakes, All rights reserved.

## Document Type

Dissertation - Restricted Access

## File Type

text

## Language

English

## Thesis Number

T 6129

## Print OCLC #

24125620

## Link to Catalog Record

Electronic access to the full-text of this document is restricted to Missouri S&T users. Otherwise, request this publication directly from Missouri S&T Library or contact your local library.

http://merlin.lib.umsystem.edu/record=b2322506~S5## Recommended Citation

Oakes, Jack L., "Algorithms and probabilistic bounds for the chromatic number of random composite graphs" (1990). *Doctoral Dissertations*. 794.

https://scholarsmine.mst.edu/doctoral_dissertations/794

Share My Dissertation If you are the author of this work and would like to grant permission to make it openly accessible to all, please click the button above.

## Comments

A report which is substantially this dissertation is available here for download.