Graph colorings / Marek Kubale, editor.

Format:

Book

Contributor:

Kubale, Marek, 1946- editor.

Series:

Contemporary mathematics (American Mathematical Society) ; v. 352.

Contemporary mathematics, 0271-4132 ; 352

Standardized Title:

Optymalizacja dyskretna. English.

Language:

English

Subjects (All):

Graph coloring.

Physical Description:

1 online resource (224 p.)

Edition:

1st ed.

Place of Publication:

Providence, Rhode Island : American Mathematical Society, [2004]

Language Note:

English

Summary:

Graph coloring is one of the oldest and best-known problems of graph theory. As people grew accustomed to applying the tools of graph theory to the solutions of real-world technological and organizational problems, new chromatic models emerged as a natural way of tackling many practical situations. Statistics show that graph coloring is one of the central issues in the collection of several hundred classical combinatorial problems. This book is devoted to problems in graph coloring,which can be viewed as one area of discrete optimization. Chapters are dedicated to various models and are largely independent of one another. In each chapter, the author highlights algorithmic aspects of the presented models, i.e., the construction of polynomial-time algorithms for graph coloring.This is an expanded and updated translation of the prizewinning book originally published in Polish, Optymalizacja dyskretna. Modele i metody kolorowania grafow. It is suitable for graduate students and researchers interested in graph theory.

Contents:

""Contents""; ""Preface""; ""Graph coloring""; ""History of graph coloring""; ""Models of graph coloring""; ""Preface to the English Edition""; ""Chapter 1. Classical Coloring of Graphs""; ""1.1. Basic terms and definitions""; ""1.2. Classical vertex-coloring""; ""1.3. Classical edge-coloring""; ""Chapter 2. On-line Coloring of Graphs""; ""2.1. On-line and off-line coloring""; ""2.2. On-line coloring algorithms""; ""2.3. Worst case effectiveness of on-line coloring""; ""2.4. Expected effectiveness of on-line coloring""; ""2.5. Susceptibility of graphs""

""2.6. Coloring of intersection graphs""""2.7. Applications to resource management""; ""Chapter 3. Equitable Coloring of Graphs""; ""3.1. Equitable vertex-coloring""; ""3.2. Equitable total coloring""; ""Chapter 4. Sum Coloring of Graphs""; ""4.1. Definition and simple properties""; ""4.2. The complexity of the sum coloring problem""; ""4.3. Generalizations of the sum coloring problem""; ""4.4. Some applications of the sum coloring problem""; ""Chapter 5. T-Coloring of Graphs""; ""5.1. The spans""; ""5.2. Sets of forbidden distances""; ""5.3. T-colorings of graphs""

""5.4. T-spans and T-chromatic numbers""""5.5. Homomorphisms and T-graphs""; ""5.6. Estimates and exact values""; ""5.7. The computational complexity""; ""5.8. Approximation algorithms""; ""5.9. Applications""; ""Chapter 6. Rank Coloring of Graphs""; ""6.1. Vertex ranking""; ""6.2. Edge ranking""; ""Chapter 7. Harmonious Coloring of Graphs""; ""7.1. Introduction""; ""7.2. Graphs with known harmonious number""; ""7.3. Bounds for the harmonious chromatic number of general graphs""; ""7.4. Algorithm Depressive""; ""7.5. Applications""; ""Chapter 8. Interval Edge-Coloring of Graphs""

""8.1. Basic properties of the model""""8.2. Consecutively colorable bipartite graphs""; ""8.3. The span of interval coloring""; ""8.4. Deficiency of graphs""; ""Chapter 9. Circular Coloring of Graphs""; ""9.1. Circular coloring of the vertices of a graph""; ""9.2. Circular coloring of the edges of a graph""; ""Chapter 10. Path Coloring and Routing in Graphs""; ""10.1. Basic definitions""; ""10.2. Known results""; ""10.3. Applications""; ""Chapter 11. List Colorings of Graphs""; ""11.1. Notation and definitions""; ""11.2. Bipartite and 2-choosable graphs""; ""11.3. The Hajós Construction""

""11.4. D-choosability and Brooks theorem""""11.5. Planar graphs""; ""11.6. Graphs for which X = Xι""; ""11.7. (k, r)-choosability""; ""11.8. Edge-list coloring""; ""Chapter 12. Ramsey Colorings of Complete Graphs""; ""12.1. Notation and basic definitions""; ""12.2. Ramsey numbers""; ""12.3. Values and properties of classical Ramsey numbers""; ""12.4. Nonclassical Ramsey numbers""; ""12.5. Applications of Ramsey numbers""; ""Chapter 13. Placing Guards in Art Galleries by Graph Coloring""; ""13.1. Introduction""; ""13.2. Fisk's proof""; ""13.3. The orthogonal art gallery theorem""

""13.4. Orthogonal polygons with holes""

Notes:

Description based upon print version of record.

Includes bibliographical references (pages 189-201) and index.

Description based on print version record.

ISBN:

0-8218-7942-1

0-8218-5687-1