Graph colorings / / Marek Kubale, editor

• Record Nr.: UNINA9910788667003321
• Pubbl/distr/stampa: Providence, Rhode Island : , : American Mathematical Society, , [2004]; ©2004
• ISBN: 0-8218-7942-1; 0-8218-5687-1
• Descrizione fisica: 1 online resource (224 p.)
• Collana: Contemporary mathematics, , 0271-4132 ; ; 352
• Disciplina: 511/.5
• Soggetti: Graph coloring
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references (pages 189-201) and index.
• Nota di contenuto: ""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""