Contents 7.2 3 The Set Chromatic Numbers of Some Classes of Graphs. 69 Lower Bounds for the Set Chromatic Number....... Multiset Colorings............. 8.1 Multiset Chromatic Number......... 8.2 Complete Multipartite Graphs 83 Graphs with Prescribed Order and Multiset Chromatic Number.. 多 8.4 Multiset Colorings Versus Set Colorings. Metric Colorings..... Metric Chre 9.3 Bounds for the Metric Chromatic Number of a Graph............. 9.4 Metric Colorings Versus Other Colorings......................... % 10 Sigma Colorings 5 10.1 Sigma Chromatic Number. 9 10.2 Sigma Colorings Versus Multiset Colorings Value a nd ra 10.4 ge...................................... r Colorings Problems 101 Modular Colorings. 11.1 ACheckerboard Problem. 11.2 Modular Colorings ................................ 105 11.3 A Lights Out Problem.. 110 11.4 Closed Modular Colorings 111 2 A Ban et Seating Problem 12.1 ts at a Cir ular Table 117 12.2 Modeling the Seating Problem Problem 120 13 Irregular Colorings....... 13.1 Irregular Chromatic Number............. 13.2 de Bruijn Sequences and Digraphs.... 128 13.3 The Irregular Chromatic Numbers of Cycles... 130 134 Nordhaus-Gaddum Inegualities.... 133 14 Recognizable Colorings 137 141 The Rec 137 143 of Graph Complete ra 14.3 Graphs with Prescribed Order and Recognition Number........... 14.4 Recognizable Colorings of Cycles and Paths ...................... 14.5 Recognizable Colorings of Trees....................... 147 References 151 Index 155 x Contents 7.2 The Set Chromatic Numbers of Some Classes of Graphs .......... 69 7.3 Lower Bounds for the Set Chromatic Number...................... 71 8 Multiset Colorings .......................................................... 75 8.1 Multiset Chromatic Number ......................................... 75 8.2 Complete Multipartite Graphs ....................................... 77 8.3 Graphs with Prescribed Order and Multiset Chromatic Number .. 79 8.4 Multiset Colorings Versus Set Colorings............................ 81 9 Metric Colorings............................................................ 85 9.1 Metric Chromatic Number ........................................... 85 9.2 Graphs with Prescribed Order and Metric Chromatic Number .... 86 9.3 Bounds for the Metric Chromatic Number of a Graph ............. 88 9.4 Metric Colorings Versus Other Colorings........................... 90 10 Sigma Colorings ............................................................ 95 10.1 Sigma Chromatic Number ........................................... 95 10.2 Sigma Colorings Versus Multiset Colorings ........................ 97 10.3 Sigma Value and Range .............................................. 98 10.4 Four Colorings Problems ............................................ 101 11 Modular Colorings ......................................................... 103 11.1 A Checkerboard Problem ............................................ 103 11.2 Modular Colorings ................................................... 105 11.3 A Lights Out Problem................................................ 110 11.4 Closed Modular Colorings........................................... 111 12 A Banquet Seating Problem ............................................... 117 12.1 Seating Students at a Circular Table................................. 117 12.2 Modeling the Seating Problem by a Graph Coloring Problem ..... 120 13 Irregular Colorings......................................................... 125 13.1 Irregular Chromatic Number......................................... 125 13.2 de Bruijn Sequences and Digraphs .................................. 128 13.3 The Irregular Chromatic Numbers of Cycles ....................... 130 13.4 Nordhaus-Gaddum Inequalities...................................... 133 14 Recognizable Colorings .................................................... 137 14.1 The Recognition Numbers of Graphs ............................... 137 14.2 Complete Multipartite Graphs ....................................... 140 14.3 Graphs with Prescribed Order and Recognition Number........... 143 14.4 Recognizable Colorings of Cycles and Paths ....................... 144 14.5 Recognizable Colorings of Trees .................................... 147 References......................................................................... 151 Index ............................................................................... 155