10CHAPTER 0.THE ORIGIN OF GRAPH COLORINGSFigure6:Ayellow-red Kempechain inthemapMthat can be reached by a green-red Kempe chain beginning at Rs.Upon doing this.ing of all regions in M (except R) is obtained, in which each neighboringa 4-coloregion of R is colored red, blue, or yellow. We can then color R green to produce a4-coloring of the entire map M. We may therefore assume that Rs can be reachedby a green-red Kempe chain that begins at Rs. (See Figure 7.)RRR3Figure 7: Yellow-red and green-red Kempe chains in the map MBecause there is a ring of regions consisting of R and a green-red Kempe chain,there cannot bea blue-yellowKempe chain in M beginning at Ry andending at RrIn addition,because thereisaring of regions consisting of R and a yellow-red Kempechain, there is no blue-green Kempe chain in M beginning at R2 and ending at Rs.Hence we interchange the colors blue and yellow for all regions in M that can bereached by ablue-yellow Kempe chain beginning at Ry and interchange the colors10 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS . . . . . . ....... ....... ....... ...... ...... ....... ...... ...... ....... ....... ... .... .... ................... .......... ........... ........... ........... ........... .. ...................................... ............................................ .. .. ... ....... ......................... ....... ..... .................................................................................. ................................... . . . .. ... ... ... ........... .... ... .. . ... .... ..... ...... ....... ................. .. ... ...... ......... ................. ...... ..... .... .. .. ......... .. .... .......... ... . . ... .. .. .... ........ .... ............................ ............... . ... ..... ...... .......... ....... ..... ... .................................... . . ................................. . ..... .... .. ..... ... ... ...... ..... ... ... . ... ... .. ........................................................ . ...................................................... ...................................................................................................................... .. . .. .. .. .. .. .................................................. .... ... .. ... .... ... ..... .......... ...... ..... ... .. ... ..... ...... ........... ....... .... .......... . .. ... ... ... .. .. ... .. ..... .. .. ... .. .. ..... . ...... . .. . .. ............................. ...................... ........................................................................................................ ...................................... .. .... ... ... .... ..... ....... ......... ....... ................ ............... ... .... ... ... .. .. ... . ....................... ............... ...... ......... .............. ... ....... ....... .... .... ......... ... .... ............ ...... ..... ... .. . .. . .................. .............. ........................... .. ..................................... . ....... ....... ...... ...... ..... .... ... ... .. . ..... . . ..... .. ... ....... .. ... .. .................................................................. .... ... ... ......................... . ............ .. ... ... ... . . ... ... .. .. . ....................................... ............................................. ......... .. .. ... . .. ... .................... ... ... ... .. .... ..... ......... ...... . .... .. ..................................................... ... .. ... .............................. .. .... .. ... .. ..... .................. .... ................. .......................... ........................ ............................ ................. ................................................... .......................... . ... .. .. .. .. R r r y y y r y r b g b R3 R4 R5 R1 R2 Figure 6: A yellow-red Kempe chain in the map M that can be reached by a green-red Kempe chain beginning at R5. Upon doing this, a 4-coloring of all regions in M (except R) is obtained, in which each neighboring region of R is colored red, blue, or yellow. We can then color R green to produce a 4-coloring of the entire map M. We may therefore assume that R3 can be reached by a green-red Kempe chain that begins at R5. (See Figure 7.) ...................................... .......... .................. ........... ...... ...... . ...... ...... ...... ...... ...... ...... ...... ...... ... ... ... ... .................... . . . . . . . . . .................................................................................... ................................. . . .. .. .. ... ... .... ........... .. ... . ... .... ..... ...... .......... .......... ... .. ... ....... ........ ............. ....... ....... ... ... ... .... . . .... .. .......... ... .. . ... .. .. .. .. ...... . ................. ............. ................ . .. ..... ...... ..... . ........... ..... ... ................................... . . . ................................ . ..... .... .. ..... ... ... ....... .... ....... . ... .. .. .. ..................................................... . ....................................................... ................................................... ............................................. ............... ....... .. .. .. ... .... . .......................................... . ...... ... .. ... .... .. .... ..... ........... ..... .... ... .. . .. .... ..... ........... ........ ... ....... .... . .. ... .... ... ... ... .. .. ...... .. .. ... .. .. .. ... . ... . . . .. . .. ............................... ....................... .......................................................................................................... .......... ......................... .. ... ... .... .... ..... ...... ................... ........... ................. ..... ... ... ... .. .. ... . ....................... ............... ...... ......... .............. ...... ...... .... ..... ........ ..... .... ............. ...... ..... ... .. .... .................. .............. ............................... .................................... . ....... ...... ....... ..... ..... ..... .... ... .. . ....... . ..... .. ... ....... .. ... .. ................................................................... ... ... . .. ....................... . .... .. ......... . . ... ... ... .. . ... ... .. .. ...................................... ............................................ .......... . . . ... .. ... ..................... . ... ... ... .. .... ..... ........ ....... . ... ... ................................................ .... .... .. ............................. . . . ..... ... ... ... .... .. ........ ....... .. .. ... ........... ...... .......................... ...................... . ........................... .................................................................... .......................... . ... ... ... .. ............................................................... ...... ........... . .... .. ... ...... .... ... .... ... .... ...... ... ................................................................................. .. ... ... ........ .. .......... . ... .................. ........ .. . . .. ..... .... ........ . . ......................... ................................. .. ..... .... . . ........................ ............... . ............................................................................................................... ..................................... . . . . .... .. ........ .... ... . .. .. .. ... ................ ... ... .. .. ........................................................................................... .. .... ....... ............... . .... ... .. .... ..... ........ . ... ......... ..... .... ........ ......... ....... .. ............................................................................ .... .. .. .. ... ........... .. ........................ . .. ....... ..... .... .... ... ... .............. ... .. .. .. ... ... ... .. .... .............. .. ................... .. .. .. .. .. .. ... .. . . ......... . . ............................................................................... .. . . . ..... ....... ... .......... ... .... ............... .. ... ..... ............ ... ... ....... ...... ..... .... ... .......... .. ... ......... ... .. ............. . ............ .. .. ... ...... ... ... ...... ... ... ...... .... ... ... ..... ................ .... y y g r r r r r y r g r g g b b y g R2 R r R4 R3 R5 R1 Figure 7: Yellow-red and green-red Kempe chains in the map M Because there is a ring of regions consisting of R and a green-red Kempe chain, there cannot be a blue-yellow Kempe chain in M beginning at R4 and ending at R1. In addition, because there is a ring of regions consisting of R and a yellow-red Kempe chain, there is no blue-green Kempe chain in M beginning at R2 and ending at R5. Hence we interchange the colors blue and yellow for all regions in M that can be reached by a blue-yellow Kempe chain beginning at R4 and interchange the colors