Graph colouring and the GraphTheory Package Mohammad Ghebleh, February 2006 restart; currentdir("/home/mamad/work/GraphTheory/GTv23"): read t: Vertex colouring: assign colours to the vertices of a graph so that adjacent vertices are coloured differently. In other words, we are interested in functions LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNjMtRiw2JVEiY0YnRi9GMi1JI21vR0YkNjBRIjpGJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRkIvJSlzdHJldGNoeUdGQi8lKnN5bW1ldHJpY0dGQi8lKGxhcmdlb3BHRkIvJS5tb3ZhYmxlbGltaXRzR0ZCLyUnYWNjZW50R0ZCLyUlZm9ybUdRJmluZml4RicvJSdsc3BhY2VHUS90aGlja21hdGhzcGFjZUYnLyUncnNwYWNlR0ZULyUobWluc2l6ZUdRIjFGJy8lKG1heHNpemVHUSlpbmZpbml0eUYnLUYsNiVRIlZGJ0YvRjItRjs2MFEiKEYnRj4vRkFGMUZDL0ZGRjFGR0ZJRktGTS9GUFEncHJlZml4RicvRlNRLnRoaW5tYXRoc3BhY2VGJy9GVlEydmVyeXRoaW5tYXRoc3BhY2VGJ0ZXRlotRiw2JVEiR0YnRi9GMi1GOzYwUSIpRidGPkZdb0ZDRl5vRkdGSUZLRk0vRlBRKHBvc3RmaXhGJ0Zhb0Zjb0ZXRlotRjs2MFEnJnJhcnI7RidGPkZARkNGXm9GR0ZJRktGTUZPRlJGVUZXRlotRjs2MFEifGZyRidGPkZdb0ZDRl5vRkdGSUZLRk1GX29GYW8vRlZGYm9GV0ZaLUkjbW5HRiQ2JEZZRj4tRjs2MFEiLEYnRj5GQC9GREYxRkVGR0ZJRktGTUZPL0ZTUSQwZW1GJy9GVlEzdmVyeXRoaWNrbWF0aHNwYWNlRidGV0ZaLUZlcDYkUSIyRidGPkZncC1GOzYwUSMuLkYnRj5GQEZDRkVGR0ZJRktGTUZbcC9GU1EwbWVkaXVtbWF0aHNwYWNlRicvRlZGXHFGV0ZaLUY7NjBRIi5GJ0Y+RkBGQ0ZFRkdGSUZLRk1GT0ZbcUZncUZXRlpGZ3AtRiw2JVEia0YnRi9GMi1GOzYwUSJ8aHJGJ0Y+Rl1vRkNGXm9GR0ZJRktGTUZbcEZhb0Zjb0ZXRlotRjs2MFExJkludmlzaWJsZVRpbWVzO0YnRj5GQEZDRkVGR0ZJRktGTUZPRlJGVUZXRlo=such that if LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEjeHlGJy8lJ2l0YWxpY0dRJXRydWVGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRic= is an edge of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEiR0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw==, then LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiUtRiw2JVEiY0YnRi9GMi1JI21vR0YkNjBRMCZBcHBseUZ1bmN0aW9uO0YnL0YzUSdub3JtYWxGJy8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGQi8lKXN0cmV0Y2h5R0ZCLyUqc3ltbWV0cmljR0ZCLyUobGFyZ2VvcEdGQi8lLm1vdmFibGVsaW1pdHNHRkIvJSdhY2NlbnRHRkIvJSVmb3JtR1EmaW5maXhGJy8lJ2xzcGFjZUdRJDBlbUYnLyUncnNwYWNlR0ZULyUobWluc2l6ZUdRIjFGJy8lKG1heHNpemVHUSlpbmZpbml0eUYnLUkobWZlbmNlZEdGJDYjLUYjNiMtRiw2JVEieEYnRi9GMkYrLUY7NjBRJSZuZTtGJ0Y+RkBGQ0ZFRkdGSUZLRk1GTy9GU1EvdGhpY2ttYXRoc3BhY2VGJy9GVkZjb0ZXRlotRiM2JUY3RjotRmhuNiMtRiM2Iy1GLDYlUSJ5RidGL0YyRis=. DrawGraph( G1 );

NkctSSlQT0xZR09OU0c2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYuNyY3JCQiK2woUVMjXCEjNkYsNyRGLCQhK2woUVMjXEYuNyRGMEYwNyRGMEYsNyY3JEYsJCIrKVFTI1w1ISIqNyRGLCQiK0NoZjImKiEjNTckRjBGOjckRjBGNjcmNyQkIitzKnotI3BGPCQiKzMkW0c6KUY8NyRGQSQiK2MwL29yRjw3JCQiKz1BWk5mRjxGRjckRklGQzcmNyQkIitUIltTLiJGOCQiK2NjKSlHQUY8NyRGTiQiKy16Mlc3Rjw3JCQiK2FPbmIkKkY8RlM3JEZWRlA3JjckJCIrOXpsXyIqRjwkIStFaGYyWEY8NyRGZW4kISt5UVMjXCZGPDckJCIrZywmeTspRjxGam43JEZdb0ZnbjcmNyQkIisvYGc3UkY8JCErTUJfLyopRjw3JEZibyQhKyczSSQqKSkqRjw3JCQiK192ekZIRjxGZ283JEZqb0ZkbzcmNyQkISthdnpGSEY8JCErS0JfLyopRjw3JEZfcEZnbzckJCErM2BnN1JGPEZnbzckRmVwRmFwNyY3JCQhK2MsJnk7KUY8JCErS2hmMlhGPDckRmpwJCErJylRUyNcJkY8NyQkISs1emxfIipGPEZfcTckRmJxRlxxNyY3JCQhK11PbmIkKkY8JCIrdWMpKUdBRjw3JEZncSQiK0F6Mlc3Rjw3JCQhK1MiW1MuIkY4RlxyNyRGX3JGaXE3JjckJCErNUFaTmZGPCQiKzskW0c6KUY8NyRGZHIkIitrMC9vckY8NyQkIStpKnotI3BGPEZpcjckRlxzRmZyLUkmQ09MT1JHRiU2QUkkUkdCR0YlIiIiIiIhRmRzRmRzRmRzRmRzRmNzRmRzRmRzRmRzRmRzRmRzRmNzRmNzRmRzRmNzRmRzRmRzRmRzRmRzRmRzRmNzRmNzRmRzRmNzRmRzRmRzRmNzRmNzRmRzLUkmU1RZTEVHRiU2I0ksUEFUQ0hOT0dSSURHRiUtSSVURVhUR0YlNiQ3JEZkc0Zkc1EiMEYoLUZqczYkNyQkRmRzRmRzJEZjc0Zkc1EiMUYoLUZqczYkNyQkIismNHd5VSdGPCQiK0tXV2d3RjxRIjJGKC1GanM2JDckJCIrSXYyWykqRjwkIit6PFtPPEY8USIzRigtRmpzNiQ3JCQiK1BTRGcnKUY8JCErLSsrK11GPFEiNEYoLUZqczYkNyQkIitHOT8/TUY8JCErNWkjcFIqRjxRIjVGKC1GanM2JDckJCErSjk/P01GPCQhKzRpI3BSKkY8USI2RigtRmpzNiQ3JCQhK0xTRGcnKUY8JCErNCsrK11GPFEiN0YoLUZqczYkNyQkIStFdjJbKSpGPCQiKyl6IltPPEY8USI4RigtRmpzNiQ3JCQhKyczd3lVJ0Y8JCIrU1dXZ3dGPFEiOUYoLUYkNiY3JEZeeEZmdy1GYHM2JkZic0Zkc0Zkc0Zjcy1JKlRISUNLTkVTU0dGJTYjIiIjLUZmczYjSSVMSU5FR0YlLUYkNiY3JEZeeEZgdEZneEZpeEZdeS1GJDYmNyRGZndGXnhGZ3hGaXhGXXktRiQ2JjckRmZ3Rl53Rmd4Rml4Rl15LUYkNiY3JEZed0Zmd0ZneEZpeEZdeS1GJDYmNyRGXndGZnZGZ3hGaXhGXXktRiQ2JjckRl53Rlx0Rmd4Rml4Rl15LUYkNiY3JEZmdkZed0ZneEZpeEZdeS1GJDYmNyRGZnZGXnZGZ3hGaXhGXXktRiQ2JjckRl52RmZ2Rmd4Rml4Rl15LUYkNiY3JEZedkZmdUZneEZpeEZdeS1GJDYmNyRGZnVGXnZGZ3hGaXhGXXktRiQ2JjckRmZ1Rl51Rmd4Rml4Rl15LUYkNiY3JEZmdUZcdEZneEZpeEZdeS1GJDYmNyRGXnVGZnVGZ3hGaXhGXXktRiQ2JjckRl51RmZ0Rmd4Rml4Rl15LUYkNiY3JEZmdEZedUZneEZpeEZdeS1GJDYmNyRGZnRGYHRGZ3hGaXhGXXktRiQ2JjckRmB0Rl54Rmd4Rml4Rl15LUYkNiY3JEZgdEZmdEZneEZpeEZdeS1GJDYmNyRGYHRGXHRGZ3hGaXhGXXktRiQ2JjckRlx0Rl53Rmd4Rml4Rl15LUYkNiY3JEZcdEZmdUZneEZpeEZdeS1GJDYmNyRGXHRGYHRGZ3hGaXhGXXktSShTQ0FMSU5HR0YoNiNJLENPTlNUUkFJTkVER0YlLUkqQVhFU1NUWUxFR0YlNiNJJU5PTkVHRiU=

There are different variations of graph colouring, e.g. edge colouring where the edges are coloured and adjacent edges must receive different colours, and total colouring where both vertices and edges are coloured. DrawGraph( G2 );

NkctSSlQT0xZR09OU0c2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYuNyY3JCQiK2woUVMjXCEjNkYsNyRGLCQhK2woUVMjXEYuNyRGMEYwNyRGMEYsNyY3JEYsJCIrKVFTI1w1ISIqNyRGLCQiK0NoZjImKiEjNTckRjBGOjckRjBGNjcmNyQkIitzKnotI3BGPCQiKzMkW0c6KUY8NyRGQSQiK2MwL29yRjw3JCQiKz1BWk5mRjxGRjckRklGQzcmNyQkIitUIltTLiJGOCQiK2NjKSlHQUY8NyRGTiQiKy16Mlc3Rjw3JCQiK2FPbmIkKkY8RlM3JEZWRlA3JjckJCIrOXpsXyIqRjwkIStFaGYyWEY8NyRGZW4kISt5UVMjXCZGPDckJCIrZywmeTspRjxGam43JEZdb0ZnbjcmNyQkIisvYGc3UkY8JCErTUJfLyopRjw3JEZibyQhKyczSSQqKSkqRjw3JCQiK192ekZIRjxGZ283JEZqb0ZkbzcmNyQkISthdnpGSEY8JCErS0JfLyopRjw3JEZfcEZnbzckJCErM2BnN1JGPEZnbzckRmVwRmFwNyY3JCQhK2MsJnk7KUY8JCErS2hmMlhGPDckRmpwJCErJylRUyNcJkY8NyQkISs1emxfIipGPEZfcTckRmJxRlxxNyY3JCQhK11PbmIkKkY8JCIrdWMpKUdBRjw3JEZncSQiK0F6Mlc3Rjw3JCQhK1MiW1MuIkY4RlxyNyRGX3JGaXE3JjckJCErNUFaTmZGPCQiKzskW0c6KUY8NyRGZHIkIitrMC9vckY8NyQkIStpKnotI3BGPEZpcjckRlxzRmZyLUkmQ09MT1JHRiU2QUkkUkdCR0YlIiIiRmNzJCIiIyEiIkZjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkcy1JJlNUWUxFR0YlNiNJLFBBVENITk9HUklER0YlLUklVEVYVEdGJTYkNyQiIiFGX3RRIjBGKC1GXHQ2JDckJEZfdEZfdCRGY3NGX3RRIjFGKC1GXHQ2JDckJCIrJjR3eVUnRjwkIitLV1dnd0Y8USIyRigtRlx0NiQ3JCQiK0l2MlspKkY8JCIrejxbTzxGPFEiM0YoLUZcdDYkNyQkIitQU0RnJylGPCQhKy0rKytdRjxRIjRGKC1GXHQ2JDckJCIrRzk/P01GPCQhKzVpI3BSKkY8USI1RigtRlx0NiQ3JCQhK0o5Pz9NRjwkISs0aSNwUipGPFEiNkYoLUZcdDYkNyQkIStMU0RnJylGPCQhKzQrKytdRjxRIjdGKC1GXHQ2JDckJCErRXYyWykqRjwkIispeiJbTzxGPFEiOEYoLUZcdDYkNyQkISsnM3d5VSdGPCQiK1NXV2d3RjxRIjlGKC1GJDYmNyRGYXhGaXctRmBzNiZGYnNGX3QkIiIoRmZzRl90LUkqVEhJQ0tORVNTR0YlNiNGZXMtRmhzNiNJJUxJTkVHRiUtRiQ2JjckRmF4RmN0LUZgczYmRmJzRmNzRl90RmNzRl55RmF5LUYkNiY3JEZpd0ZheEZqeEZeeUZheS1GJDYmNyRGaXdGYXctRmBzNiZGYnNGX3QkIiImRmZzRmNzRl55RmF5LUYkNiY3JEZhd0Zpd0ZfekZeeUZheS1GJDYmNyRGYXdGaXZGanhGXnlGYXktRiQ2JjckRmF3Rl50Rmd5Rl55RmF5LUYkNiY3JEZpdkZhd0ZqeEZeeUZheS1GJDYmNyRGaXZGYXZGZ3lGXnlGYXktRiQ2JjckRmF2Rml2Rmd5Rl55RmF5LUYkNiY3JEZhdkZpdUZfekZeeUZheS1GJDYmNyRGaXVGYXZGX3pGXnlGYXktRiQ2JjckRml1RmF1Rmd5Rl55RmF5LUYkNiY3JEZpdUZedEZqeEZeeUZheS1GJDYmNyRGYXVGaXVGZ3lGXnlGYXktRiQ2JjckRmF1Rml0Rl96Rl55RmF5LUYkNiY3JEZpdEZhdUZfekZeeUZheS1GJDYmNyRGaXRGY3RGanhGXnlGYXktRiQ2JjckRmN0RmF4Rmd5Rl55RmF5LUYkNiY3JEZjdEZpdEZqeEZeeUZheS1GJDYmNyRGY3RGXnRGX3pGXnlGYXktRiQ2JjckRl50RmF3Rmd5Rl55RmF5LUYkNiY3JEZedEZpdUZqeEZeeUZheS1GJDYmNyRGXnRGY3RGX3pGXnlGYXktSShTQ0FMSU5HR0YoNiNJLENPTlNUUkFJTkVER0YlLUkqQVhFU1NUWUxFR0YlNiNJJU5PTkVHRiU=

DrawGraph( G3 );

NkctSSlQT0xZR09OU0c2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYuNyY3JCQiK2woUVMjXCEjNkYsNyRGLCQhK2woUVMjXEYuNyRGMEYwNyRGMEYsNyY3JEYsJCIrKVFTI1w1ISIqNyRGLCQiK0NoZjImKiEjNTckRjBGOjckRjBGNjcmNyQkIitzKnotI3BGPCQiKzMkW0c6KUY8NyRGQSQiK2MwL29yRjw3JCQiKz1BWk5mRjxGRjckRklGQzcmNyQkIitUIltTLiJGOCQiK2NjKSlHQUY8NyRGTiQiKy16Mlc3Rjw3JCQiK2FPbmIkKkY8RlM3JEZWRlA3JjckJCIrOXpsXyIqRjwkIStFaGYyWEY8NyRGZW4kISt5UVMjXCZGPDckJCIrZywmeTspRjxGam43JEZdb0ZnbjcmNyQkIisvYGc3UkY8JCErTUJfLyopRjw3JEZibyQhKyczSSQqKSkqRjw3JCQiK192ekZIRjxGZ283JEZqb0ZkbzcmNyQkISthdnpGSEY8JCErS0JfLyopRjw3JEZfcEZnbzckJCErM2BnN1JGPEZnbzckRmVwRmFwNyY3JCQhK2MsJnk7KUY8JCErS2hmMlhGPDckRmpwJCErJylRUyNcJkY8NyQkISs1emxfIipGPEZfcTckRmJxRlxxNyY3JCQhK11PbmIkKkY8JCIrdWMpKUdBRjw3JEZncSQiK0F6Mlc3Rjw3JCQhK1MiW1MuIkY4RlxyNyRGX3JGaXE3JjckJCErNUFaTmZGPCQiKzskW0c6KUY8NyRGZHIkIitrMC9vckY8NyQkIStpKnotI3BGPEZpcjckRlxzRmZyLUkmQ09MT1JHRiU2QUkkUkdCR0YlIiIiIiIhRmRzRmRzRmRzRmRzRmNzRmRzRmRzRmRzRmRzRmRzRmNzRmNzRmRzRmNzRmRzRmRzRmRzRmRzRmRzRmNzRmNzRmRzRmNzRmRzRmRzRmNzRmNzRmRzLUkmU1RZTEVHRiU2I0ksUEFUQ0hOT0dSSURHRiUtSSVURVhUR0YlNiQ3JEZkc0Zkc1EiMEYoLUZqczYkNyQkRmRzRmRzJEZjc0Zkc1EiMUYoLUZqczYkNyQkIismNHd5VSdGPCQiK0tXV2d3RjxRIjJGKC1GanM2JDckJCIrSXYyWykqRjwkIit6PFtPPEY8USIzRigtRmpzNiQ3JCQiK1BTRGcnKUY8JCErLSsrK11GPFEiNEYoLUZqczYkNyQkIitHOT8/TUY8JCErNWkjcFIqRjxRIjVGKC1GanM2JDckJCErSjk/P01GPCQhKzRpI3BSKkY8USI2RigtRmpzNiQ3JCQhK0xTRGcnKUY8JCErNCsrK11GPFEiN0YoLUZqczYkNyQkIStFdjJbKSpGPCQiKyl6IltPPEY8USI4RigtRmpzNiQ3JCQhKyczd3lVJ0Y8JCIrU1dXZ3dGPFEiOUYoLUYkNiY3JEZeeEZmdy1GYHM2JkZic0ZkcyQiIighIiJGZHMtSSpUSElDS05FU1NHRiU2IyIiIy1GZnM2I0klTElORUdGJS1GJDYmNyRGXnhGYHQtRmBzNiZGYnNGY3NGZHNGY3NGXHlGYHktRiQ2JjckRmZ3Rl54Rmd4Rlx5RmB5LUYkNiY3JEZmd0Zedy1GYHM2JkZic0ZkcyQiIiZGW3lGY3NGXHlGYHktRiQ2JjckRl53RmZ3Rl56Rlx5RmB5LUYkNiY3JEZed0ZmdkZneEZceUZgeS1GJDYmNyRGXndGXHRGZnlGXHlGYHktRiQ2JjckRmZ2Rl53Rmd4Rlx5RmB5LUYkNiY3JEZmdkZedkZmeUZceUZgeS1GJDYmNyRGXnZGZnZGZnlGXHlGYHktRiQ2JjckRl52RmZ1Rl56Rlx5RmB5LUYkNiY3JEZmdUZedkZeekZceUZgeS1GJDYmNyRGZnVGXnVGZnlGXHlGYHktRiQ2JjckRmZ1Rlx0Rmd4Rlx5RmB5LUYkNiY3JEZedUZmdUZmeUZceUZgeS1GJDYmNyRGXnVGZnRGXnpGXHlGYHktRiQ2JjckRmZ0Rl51Rl56Rlx5RmB5LUYkNiY3JEZmdEZgdEZneEZceUZgeS1GJDYmNyRGYHRGXnhGZnlGXHlGYHktRiQ2JjckRmB0RmZ0Rmd4Rlx5RmB5LUYkNiY3JEZgdEZcdEZeekZceUZgeS1GJDYmNyRGXHRGXndGZnlGXHlGYHktRiQ2JjckRlx0RmZ1Rmd4Rlx5RmB5LUYkNiY3JEZcdEZgdEZeekZceUZgeS1JKFNDQUxJTkdHRig2I0ksQ09OU1RSQUlORURHRiUtSSpBWEVTU1RZTEVHRiU2I0klTk9ORUdGJQ==

Both vertex and edge colouring problems are NP-Complete when the number of colours is at least 3. In the GraphTheory package, brute-force search procedures are implemented for checking colourability. Using bounds helps to speed up the search. ChromaticNumberBound(G1);

OyIiJEYj

The upper bound is computed in linear time in terms of the number of vertices of the graph (GreedyColor), but the lower bound can take a lot of time since it uses two NP-Complete invariants of the graph, namely the clique number and independence number. Polynomial-time algorithms exist for some special cases of graph colouring. For example checking 2-colourability can be done in LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiYtRiw2JVEiT0YnL0YwUSZmYWxzZUYnL0YzUSdub3JtYWxGJy1JI21vR0YkNjBRIihGJ0Y8LyUmZmVuY2VHRjEvJSpzZXBhcmF0b3JHRjsvJSlzdHJldGNoeUdGMS8lKnN5bW1ldHJpY0dGOy8lKGxhcmdlb3BHRjsvJS5tb3ZhYmxlbGltaXRzR0Y7LyUnYWNjZW50R0Y7LyUlZm9ybUdRJ3ByZWZpeEYnLyUnbHNwYWNlR1EudGhpbm1hdGhzcGFjZUYnLyUncnNwYWNlR1EydmVyeXRoaW5tYXRoc3BhY2VGJy8lKG1pbnNpemVHUSIxRicvJShtYXhzaXplR1EpaW5maW5pdHlGJy1GLDYlUSJuRidGL0YyLUY/NjBRIilGJ0Y8RkJGREZGRkhGSkZMRk4vRlFRKHBvc3RmaXhGJ0ZTRlZGWUZmbkYr time (IsBipartite). Another example is the edge chromatic number (chromatic index) of bipartite graphs which can be done in polynomial time using the maximum network flow algorithm (ChromaticIndex). Let LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEiR0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== be a bipartite graph with \316\224 := MaximumDegree(G). It is known that the chromatic index of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEiR0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== is equal to \316\224. To find an optimal edge colouring we need to partition the edges into \316\224 disjoint matchings. In the following we show how one such matching can be found. With some careful consideration this method is used in ChromaticIndex to calculate the chromatic index and find an optimal edge colouring of any bipartite graph. a, b := 4, 6: G := RandomBipartiteGraph([a, b], .6);

LUkoR1JBUEhMTkclKnByb3RlY3RlZEc2KEkrdW5kaXJlY3RlZEdGJEkrdW53ZWlnaHRlZEdGJDcsIiIiIiIjIiIkIiIlIiImIiInIiIoIiIpIiIqIiM1LUkmQXJyYXlHRiQ2Iy9JJCVpZEc2IiIqL2ooZThJMEdSQVBITE4vdGFibGUvOEdGOCIiIQ==

E := map(convert, Edges(G), list);

PDI3JCIiJSIiJzckIiIjIiIoNyRGJ0YlNyRGJyIjNTckIiIkRiU3JCIiIiIiJjckRi9GKDckRi8iIio3JEYvRis3JEYnRjA3JEYtRjM3JEYtRis3JEYkIiIpNyRGJEYwNyRGLUY5NyRGJEYz

V := [op(Vertices(G)), s, t]: E := map( e->[e,1], E) union {seq([[s,i],1], i=1..a)} union {seq([[j,t],1], j=a+1..a+b)}: N := Graph( V, E );

LUkoR1JBUEhMTkclKnByb3RlY3RlZEc2KEkpZGlyZWN0ZWRHRiRJKXdlaWdodGVkR0YkNy4iIiIiIiMiIiQiIiUiIiYiIiciIigiIikiIioiIzVJInNHNiJJInRHRjQtSSZBcnJheUdGJDYjL0kkJWlkR0Y0Iio7VmhQIkkwR1JBUEhMTi90YWJsZS85R0Y0LUknTWF0cml4RzYkRiRJKF9zeXNsaWJHRjQ2Iy9GOiIqY14zUCI=

DrawNetwork( N, s, t );

NkstSSlQT0xZR09OU0c2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYwNyY3JCQiK1ZyJnlFJCEjNSQhK2RHOUtkRi43JEYsJCErVnImeUUnRi43JCQiK2RHOUtGRi5GMjckRjVGLzcmNyQkIitWciZ5RSdGLkYvNyRGOkYyNyQkIitkRzlLZEYuRjI3JEY+Ri83JjckJCIrVnImeUUqRi5GLzckRkNGMjckJCIrZEc5SygpRi5GMjckRkdGLzcmNyQkIis5ZHlFNyEiKkYvNyRGTEYyNyQkIisnRzlLPCJGTkYyNyRGUUYvNyY3JCQiKydHOTJUI0YuJCErZEc5SygpRi43JEZWJCErVnImeUUqRi43JCQiKysrK3Y9Ri5GZW43JEZobkZYNyY3JCQiK0g5ZGBYRi5GWDckRl1vRmVuNyQkIitWciZ5LCVGLkZlbjckRmFvRlg3JjckJCIrcyZHa3AnRi5GWDckRmZvRmVuNyQkIisnRzkyOydGLkZlbjckRmpvRlg3JjckJCIrOWRHUikpRi5GWDckRl9wRmVuNyQkIitHOWQuJClGLkZlbjckRmNwRlg3JjckJCIrJkc5Iyk0IkZORlg3JEZocEZlbjckJCIrZEdrVzVGTkZlbjckRlxxRlg3JjckJCIrKytdNzhGTkZYNyRGYXFGZW43JCQiK3MmRyplN0ZORmVuNyRGZXFGWDcmNyQkIitWciZ5dyhGLiQhK2RHOUtGRi43JEZqcSQhK1ZyJnlFJEYuNyQkIitkRzlLc0YuRl9yNyRGYnJGXHI3JjckRmpxJCErJ0c5SzwiRk43JEZqcSQhKzlkeUU3Rk43JEZickZqcjckRmJyRmdyLUkmQ09MT1JHRiU2R0kkUkdCR0YlIiIiRmJzJCIiIyEiIkZic0Zic0Zjc0Zic0Zic0Zjc0Zic0Zic0Zjc0Zic0Zic0Zjc0Zic0Zic0Zjc0Zic0Zic0Zjc0Zic0Zic0Zjc0Zic0Zic0Zjc0Zic0Zic0Zjc0Zic0Zic0Zjc0Zic0Zic0Zjcy1JJlNUWUxFR0YlNiNJLFBBVENITk9HUklER0YlLUklVEVYVEdGJTYkNyQkIisrKysrSUYuJCErKysrK2dGLlEiMUYoLUZbdDYkNyQkIisrKysrZ0YuRmB0USIyRigtRlt0NiQ3JCQiKysrKyshKkYuRmB0USIzRigtRlt0NiQ3JCQiKysrKys3Rk5GYHRRIjRGKC1GW3Q2JDckJCIrVnImRzkjRi4kISsrKysrISpGLlEiNUYoLUZbdDYkNyQkIisnRzlkRyVGLkZqdVEiNkYoLUZbdDYkNyQkIitIOWRHa0YuRmp1USI3RigtRlt0NiQ3JCQiK3ImRzlkKUYuRmp1USI4RigtRlt0NiQ3JCQiK3ImRzkyIkZORmp1USI5RigtRlt0NiQ3JCQiKydHOWRHIkZORmp1USMxMEYoLUZbdDYkNyQkIisrKysrdkYuJCErKysrK0lGLlEic0YoLUZbdDYkNyRGXngkISsrKysrN0ZOUSJ0RigtRiQ2KDckRl14RmF1NyQ3JCQiKysrKyslKUYuJCErKysrK09GLjckJCIrJVJXNkEpRi4kIStdKUdITCRGLjckRl15NyQkIituQG8lMylGLiQhKyI+QXdgJEYuLUZfczYmRmFzIiIhRl96RmJzLUkqVEhJQ0tORVNTR0YlNiNGZHMtRmdzNiNJJUxJTkVHRiUtRiQ2KDckRl14Rlt1NyQ3JCQiKysrKyt5Ri5GYHk3JCQiK1dVQHh4Ri4kISt3K1F6S0YuNyRGano3JCQiKzliPGR2Ri4kIStTJSpSKlEkRi5GXXpGYHpGY3otRiQ2KDckRl14RmV0NyQ3JCQiKysrKytzRi5GYHk3JCQiKydbQ0dXKEYuRmZbbDckRlxcbDckJCIrY2R5QXNGLkZgW2xGXXpGYHpGY3otRiQ2KDckRl14Rl10NyQ3JCQiKysrKyttRi5GYHk3JCQiK0x5SjpwRi5GW3o3JEZqXGw3JCQiKzFjJil5bkYuRmV5Rl16RmB6RmN6LUYkNig3JEZnd0ZleDckNyQkIitIOWR5NkZOJCErKysrKycqRi43JCQiK2s6XDU3Rk4kIStobUFpJipGLjckRmhdbDckJCIrJVJyJSk+IkZOJCEreDJlWiQqRi5GXXpGYHpGY3otRiQ2KDckRmF3RmV4NyQ3JCQiK2RHOTI1Rk5GW15sNyQkIitdX0NQNUZOJCErUTtJKFsqRi43JEZcX2w3JCQiKydbZi8tIkZOJCEraVRYMiQqRi5GXXpGYHpGY3otRiQ2KDckRlt3RmV4NyQ3JCQiK2RHOWQkKUYuRltebDckJCIrdTUnR2QpRi4kISsyLnJoJCpGLjckRl5gbDckJCIrOEM9VCQpRi4kIStHeicqeSMqRi5GXXpGYHpGY3otRiQ2KDckRmV2RmV4NyQ3JCQiK1ZyJkdrJ0YuRltebDckJCIrKGU8KWVtRi5GamBsNyRGYGFsNyQkIitFKlFyVSdGLkZkYGxGXXpGYHpGY3otRiQ2KDckRl92RmV4NyQ3JCQiK0g5ZEdcRi5GW15sNyQkIitXXlMmeiVGLkZoX2w3JEZeYmw3JCQiKyt2YUZZRi5GYl9sRl16RmB6RmN6LUYkNig3JEZndUZleDckNyQkIis5ZEc5S0YuRltebDckJCIrZ2dHOklGLkZmXmw3JEZcY2w3JCQiK2xWMyYqR0YuRmBebEZdekZgekZjei1GJDYoNyRGYXVGYXc3JDckJCIrOWRHdTZGTiQhKysrKyttRi43JCQiK3ImKkcoPiJGTiQhKzlQXXZqRi43JEZqY2w3JCQiKzh3bnU2Rk4kISs/YGZ5aUYuRl16RmB6RmN6LUYkNig3JEZhdUZbdzckNyQkIityJkc5OCJGTkZdZGw3JCQiK1lyKD07IkZOJCErPjEtKFwnRi43JEZeZWw3JCQiK0Jzblg2Rk4kIStTJ3k9SidGLkZdekZgekZjei1GJDYoNyRGYXVGX3Y3JDckJCIrJ0c5ZC8iRk5GXWRsNyQkIisrJlx5MiJGTiQhKyM0NHFnJ0YuNyRGYGZsNyQkIitLSCQqbzVGTiQhKykqZXN4akYuRl16RmB6RmN6LUYkNig3JEZhdUZndTckNyQkIitWciZHKyJGTkZdZGw3JCQiKyk0W1suIkZOJCErPEJASm1GLjckRmJnbDckJCIrM19vRjVGTiQhK0otJ2VSJ0YuRl16RmB6RmN6LUYkNig3JEZbdUZndzckNyQkIitzJkc5eCpGLkZdZGw3JCQiK0smUkRoKkYuJCErTSkpZT9qRi43JEZkaGw3JCQiK0NOXWglKkYuJCErKCl6eDlsRi5GXXpGYHpGY3otRiQ2KDckRlt1RmF3NyQ3JCQiK1VyJkdNKkYuRl1kbDckJCIrdTtLLSQqRi4kIStWdzgiRydGLjckRmZpbDckJCIrLlhzKTMqRi4kIStwSj4ua0YuRl16RmB6RmN6LUYkNig3JEZbdUZbdzckNyQkIis5ZEc5KilGLkZdZGw3JCQiKy46MHkhKkYuJCErQSo9TUsnRi43JEZoamw3JCQiK2VLXk0pKUYuJCErV3hpKUcnRi5GXXpGYHpGY3otRiQ2KDckRlt1Rl92NyQ3JCQiK2RHOWQhKUYuRl1kbDckJCIrSWlydCQpRi4kISt4T01XbEYuNyRGalttNyQkIitzIVI7QylGLiQhK2VRek9qRi5GXXpGYHpGY3otRiQ2KDckRmV0Rmd3NyQ3JCQiK3MmRzlQKEYuRl1kbDckJCIrJj5vJ1tyRi4kIStQK0dvakYuNyRGXF1tNyQkIitVQzFdcUYuJCErO1ltJGYnRi5GXXpGYHpGY3otRiQ2KDckRmV0RmV2NyQ3JCQiKydHOWQzJ0YuRl1kbDckJCIrVW5bbGhGLkZkW203JEZeXm03JCQiKyhcWz4jZkYuRl5bbUZdekZgekZjei1GJDYoNyRGZXRGX3Y3JDckJCIrZEc5ZGNGLkZdZGw3JCQiKydcdjciZkYuJCErcUo+LmtGLjckRlxfbTckJCIrRCR5d3AmRi5GXGpsRl16RmB6RmN6LUYkNig3JEZldEZndTckNyQkIitIOWRHX0YuRl1kbDckJCIreGtcUWJGLkZgaWw3JEZcYG03JCQiK3AvWShRJkYuRmpobEZdekZgekZjei1GJDYoNyRGXXRGZ3c3JDckJCIrcyZHOShcRi5GXWRsNyQkIitAejlCWkYuJCErSy0nZVInRi43JEZqYG03JCQiK0UhPjpsJUYuRmhnbEZdekZgekZjei1GJDYoNyRGXXRGYXc3JDckJCIrVXImR2ElRi5GXWRsNyQkIisob3ExSiVGLkZcZ2w3JEZqYW03JCQiKytdXUBVRi5GZmZsRl16RmB6RmN6LUYkNig3JEZddEZldjckNyQkIisnRzlkbyRGLkZdZGw3JCQiK2t4QVZORi5GamVsNyRGaGJtNyQkIitMJkc3USRGLkZkZWxGXXpGYHpGY3otRiQ2KDckRl10Rmd1NyQ3JCQiK0g5ZEdHRi5GXWRsNyQkIislZkQlR0lGLiQhKyl6YyNbakYuNyRGZmNtNyQkIitSLik9eiNGLiQhK1NDbiFHJ0YuRl16RmB6RmN6LUkoU0NBTElOR0dGKDYjSSxDT05TVFJBSU5FREdGJS1JKkFYRVNTVFlMRUdGJTYjSSVOT05FR0Yl

MaxFlow( N, s, t, 'f' );

IiIl

lprint( f );

Matrix(12, 12, {(3, 6) = 1, (4, 5) = 1, (11, 1) = 1, (11, 4) = 1, (1, 9) = 1, (7, 12) = 1, (9, 12) = 1, (6, 12) = 1, (11, 2) = 1, (11, 3) = 1, (2, 7) = 1, (5, 12) = 1}, datatype = anything, storage = sparse, order = Fortran_order, shape = [])

M := {seq(seq(`if`(f[i,j]=1, {i,j}, NULL), i=1..10), j=1..10)};

PCY8JCIiIiIiKjwkIiIjIiIoPCQiIiQiIic8JCIiJSIiJg==

Circular Colouring Let LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEia0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== and LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEiZEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== be relatively prime, with LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkmbWZyYWNHRiQ2KC1GLDYlUSJrRidGL0YyLUYsNiVRImRGJ0YvRjIvJS5saW5ldGhpY2tuZXNzR1EiMUYnLyUrZGVub21hbGlnbkdRJ2NlbnRlckYnLyUpbnVtYWxpZ25HRkMvJSliZXZlbGxlZEdRJmZhbHNlRidGKy1JI21vR0YkNjBRNCZHcmVhdGVyU2xhbnRFcXVhbDtGJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdGSC8lKnNlcGFyYXRvckdGSC8lKXN0cmV0Y2h5R0ZILyUqc3ltbWV0cmljR0ZILyUobGFyZ2VvcEdGSC8lLm1vdmFibGVsaW1pdHNHRkgvJSdhY2NlbnRHRkgvJSVmb3JtR1EmaW5maXhGJy8lJ2xzcGFjZUdRL3RoaWNrbWF0aHNwYWNlRicvJSdyc3BhY2VHRlxvLyUobWluc2l6ZUdRIjFGJy8lKG1heHNpemVHUSlpbmZpbml0eUYnLUkjbW5HRiQ2JFEjMi5GJ0ZN A LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkobWZlbmNlZEdGJDYjLUYjNiUtRiw2JVEia0YnRi9GMi1JI21vR0YkNjBRIixGJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRjEvJSlzdHJldGNoeUdGRS8lKnN5bW1ldHJpY0dGRS8lKGxhcmdlb3BHRkUvJS5tb3ZhYmxlbGltaXRzR0ZFLyUnYWNjZW50R0ZFLyUlZm9ybUdRJmluZml4RicvJSdsc3BhY2VHUSQwZW1GJy8lJ3JzcGFjZUdRM3Zlcnl0aGlja21hdGhzcGFjZUYnLyUobWluc2l6ZUdRIjFGJy8lKG1heHNpemVHUSlpbmZpbml0eUYnLUYsNiVRImRGJ0YvRjJGKw==-colouring of a graph LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEiR0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== is a function LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNjctRiw2JVEiY0YnRi9GMi1JI21vR0YkNjBRIjpGJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRkIvJSlzdHJldGNoeUdGQi8lKnN5bW1ldHJpY0dGQi8lKGxhcmdlb3BHRkIvJS5tb3ZhYmxlbGltaXRzR0ZCLyUnYWNjZW50R0ZCLyUlZm9ybUdRJmluZml4RicvJSdsc3BhY2VHUS90aGlja21hdGhzcGFjZUYnLyUncnNwYWNlR0ZULyUobWluc2l6ZUdRIjFGJy8lKG1heHNpemVHUSlpbmZpbml0eUYnLUYsNiVRIlZGJ0YvRjItRjs2MFEiKEYnRj4vRkFGMUZDL0ZGRjFGR0ZJRktGTS9GUFEncHJlZml4RicvRlNRLnRoaW5tYXRoc3BhY2VGJy9GVlEydmVyeXRoaW5tYXRoc3BhY2VGJ0ZXRlotRiw2JVEiR0YnRi9GMi1GOzYwUSIpRidGPkZdb0ZDRl5vRkdGSUZLRk0vRlBRKHBvc3RmaXhGJ0Zhb0Zjb0ZXRlotRjs2MFEnJnJhcnI7RidGPkZARkNGXm9GR0ZJRktGTUZPRlJGVUZXRlotRjs2MFEifGZyRidGPkZdb0ZDRl5vRkdGSUZLRk1GX29GYW8vRlZGYm9GV0ZaLUkjbW5HRiQ2JFEiMEYnRj4tRjs2MFEiLEYnRj5GQC9GREYxRkVGR0ZJRktGTUZPL0ZTUSQwZW1GJy9GVlEzdmVyeXRoaWNrbWF0aHNwYWNlRidGV0ZaLUZlcDYkRllGPkZocC1GZXA2JFEiMkYnRj5GaHAtRjs2MFEjLi5GJ0Y+RkBGQ0ZFRkdGSUZLRk1GW3AvRlNRMG1lZGl1bW1hdGhzcGFjZUYnL0ZWRl1xRldGWi1GOzYwUSIuRidGPkZARkNGRUZHRklGS0ZNRk9GXHFGanFGV0ZaRmhwLUYsNiVRImtGJ0YvRjItRjs2MFEoJm1pbnVzO0YnRj5GQEZbcUZFRkdGSUZLRk1GT0ZccUZecUZXRlpGYHEtRjs2MFEifGhyRidGPkZdb0ZDRl5vRkdGSUZLRk1GW3BGYW9GY29GV0ZaLUY7NjBRMSZJbnZpc2libGVUaW1lcztGJ0Y+RkBGQ0ZFRkdGSUZLRk1GT0ZSRlVGV0Zasuch that if LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEjeHlGJy8lJ2l0YWxpY0dRJXRydWVGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRic= is an edge of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEiR0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== then LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYuLUkjbWlHRiQ2JVEiZEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNjBRMSZMZXNzU2xhbnRFcXVhbDtGJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUlZm9ybUdRJmluZml4RicvJSdsc3BhY2VHUS90aGlja21hdGhzcGFjZUYnLyUncnNwYWNlR0ZPLyUobWluc2l6ZUdRIjFGJy8lKG1heHNpemVHUSlpbmZpbml0eUYnLUYjNictRjY2MFEifGdyRidGOUY7Rj4vRkFGMUZCRkRGRkZIRkovRk5RMnZlcnl0aGlubWF0aHNwYWNlRicvRlFGaW5GUkZVLUYsNiVRImNGJ0YvRjItRjY2MFEwJkFwcGx5RnVuY3Rpb247RidGOUY7Rj5GQEZCRkRGRkZIRkovRk5RJDBlbUYnL0ZRRmJvRlJGVS1JKG1mZW5jZWRHRiQ2Iy1GIzYjLUYsNiVRInhGJ0YvRjItRiw2JVEhRidGL0YyLUY2NjBRKCZtaW51cztGJ0Y5RjsvRj9GMUZARkJGREZGRkhGSkZhby9GUVEzdmVyeXRoaWNrbWF0aHNwYWNlRidGUkZVLUYjNiVGW29GXm8tRmVvNiMtRiM2Iy1GLDYlUSJ5RidGL0YyRlxwRlpGNS1GLDYlUSJrRidGL0YyRl9wRitGXHA=. DrawGraph(G0);

NkctSSlQT0xZR09OU0c2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYuNyY3JCQiK2woUVMjXCEjNkYsNyRGLCQhK2woUVMjXEYuNyRGMEYwNyRGMEYsNyY3JEYsJCIrKVFTI1w1ISIqNyRGLCQiK0NoZjImKiEjNTckRjBGOjckRjBGNjcmNyQkIitzKnotI3BGPCQiKzMkW0c6KUY8NyRGQSQiK2MwL29yRjw3JCQiKz1BWk5mRjxGRjckRklGQzcmNyQkIitUIltTLiJGOCQiK2NjKSlHQUY8NyRGTiQiKy16Mlc3Rjw3JCQiK2FPbmIkKkY8RlM3JEZWRlA3JjckJCIrOXpsXyIqRjwkIStFaGYyWEY8NyRGZW4kISt5UVMjXCZGPDckJCIrZywmeTspRjxGam43JEZdb0ZnbjcmNyQkIisvYGc3UkY8JCErTUJfLyopRjw3JEZibyQhKyczSSQqKSkqRjw3JCQiK192ekZIRjxGZ283JEZqb0ZkbzcmNyQkISthdnpGSEY8JCErS0JfLyopRjw3JEZfcEZnbzckJCErM2BnN1JGPEZnbzckRmVwRmFwNyY3JCQhK2MsJnk7KUY8JCErS2hmMlhGPDckRmpwJCErJylRUyNcJkY8NyQkISs1emxfIipGPEZfcTckRmJxRlxxNyY3JCQhK11PbmIkKkY8JCIrdWMpKUdBRjw3JEZncSQiK0F6Mlc3Rjw3JCQhK1MiW1MuIkY4RlxyNyRGX3JGaXE3JjckJCErNUFaTmZGPCQiKzskW0c6KUY8NyRGZHIkIitrMC9vckY8NyQkIStpKnotI3BGPEZpcjckRlxzRmZyLUkmQ09MT1JHRiU2QUkkUkdCR0YlIiIiRmNzJCIiIyEiIkZjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkc0Zjc0Zjc0Zkcy1JJlNUWUxFR0YlNiNJLFBBVENITk9HUklER0YlLUklVEVYVEdGJTYkNyQiIiFGX3RRIjFGKC1GXHQ2JDckJEZfdEZfdCRGY3NGX3RRIjJGKC1GXHQ2JDckJCIrJjR3eVUnRjwkIitLV1dnd0Y8USIzRigtRlx0NiQ3JCQiK0l2MlspKkY8JCIrejxbTzxGPFEiNEYoLUZcdDYkNyQkIitQU0RnJylGPCQhKy0rKytdRjxRIjVGKC1GXHQ2JDckJCIrRzk/P01GPCQhKzVpI3BSKkY8USI2RigtRlx0NiQ3JCQhK0o5Pz9NRjwkISs0aSNwUipGPFEiN0YoLUZcdDYkNyQkIStMU0RnJylGPCQhKzQrKytdRjxRIjhGKC1GXHQ2JDckJCErRXYyWykqRjwkIispeiJbTzxGPFEiOUYoLUZcdDYkNyQkISsnM3d5VSdGPCQiK1NXV2d3RjxRIzEwRigtRiQ2JjckRmF4Rml3LUZgczYmRmJzRl90Rl90RmNzLUkqVEhJQ0tORVNTR0YlNiNGZXMtRmhzNiNJJUxJTkVHRiUtRiQ2JjckRmF4RmN0Rmp4Rlx5Rl95LUYkNiY3JEZpd0ZheEZqeEZceUZfeS1GJDYmNyRGaXdGYXdGanhGXHlGX3ktRiQ2JjckRmF3Rml3Rmp4Rlx5Rl95LUYkNiY3JEZhd0ZpdkZqeEZceUZfeS1GJDYmNyRGYXdGXnRGanhGXHlGX3ktRiQ2JjckRml2RmF3Rmp4Rlx5Rl95LUYkNiY3JEZpdkZhdkZqeEZceUZfeS1GJDYmNyRGYXZGaXZGanhGXHlGX3ktRiQ2JjckRmF2Rml1Rmp4Rlx5Rl95LUYkNiY3JEZpdUZhdkZqeEZceUZfeS1GJDYmNyRGaXVGYXVGanhGXHlGX3ktRiQ2JjckRml1Rl50Rmp4Rlx5Rl95LUYkNiY3JEZhdUZpdUZqeEZceUZfeS1GJDYmNyRGYXVGaXRGanhGXHlGX3ktRiQ2JjckRml0RmF1Rmp4Rlx5Rl95LUYkNiY3JEZpdEZjdEZqeEZceUZfeS1GJDYmNyRGY3RGYXhGanhGXHlGX3ktRiQ2JjckRmN0Rml0Rmp4Rlx5Rl95LUYkNiY3JEZjdEZedEZqeEZceUZfeS1GJDYmNyRGXnRGYXdGanhGXHlGX3ktRiQ2JjckRl50Rml1Rmp4Rlx5Rl95LUYkNiY3JEZedEZjdEZqeEZceUZfeS1JKFNDQUxJTkdHRig2I0ksQ09OU1RSQUlORURHRiUtSSpBWEVTU1RZTEVHRiU2I0klTk9ORUdGJQ==

IsKDColorable( G0, 8, 3 );

SSV0cnVlRyUqcHJvdGVjdGVkRw==

IsKDColorable( G0, 7, 3 );

SSZmYWxzZUclKnByb3RlY3RlZEc=

The circular chromatic number of a graph is the infimum of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkmbWZyYWNHRiQ2KC1GLDYlUSJrRidGL0YyLUYsNiVRImRGJ0YvRjIvJS5saW5ldGhpY2tuZXNzR1EiMUYnLyUrZGVub21hbGlnbkdRJ2NlbnRlckYnLyUpbnVtYWxpZ25HRkMvJSliZXZlbGxlZEdRJmZhbHNlRidGKw== over all values of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEia0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== and LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEiZEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== such that the graph is LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkobWZlbmNlZEdGJDYjLUYjNiUtRiw2JVEia0YnRi9GMi1JI21vR0YkNjBRIixGJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRjEvJSlzdHJldGNoeUdGRS8lKnN5bW1ldHJpY0dGRS8lKGxhcmdlb3BHRkUvJS5tb3ZhYmxlbGltaXRzR0ZFLyUnYWNjZW50R0ZFLyUlZm9ybUdRJmluZml4RicvJSdsc3BhY2VHUSQwZW1GJy8lJ3JzcGFjZUdRM3Zlcnl0aGlja21hdGhzcGFjZUYnLyUobWluc2l6ZUdRIjFGJy8lKG1heHNpemVHUSlpbmZpbml0eUYnLUYsNiVRImRGJ0YvRjJGKw==-colourable. CircularChromaticNumber( G0, 'col' );

IyIiKSIiJA==

col;

NywiIiEiIiQiIiciIiIiIiUiIigiIiMiIiZGJkYl

CircularChromaticIndex( G0 );

IiIk

Pete := SpecialGraphs:-PetersenGraph(): DrawGraph( Pete );

Nk0tSSlQT0xZR09OU0c2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYuNyY3JCQiKyNlI0diWiEjNiQiK0VHYlo1ISIqNyRGLCQiK1U8WkMmKiEjNTckJCErI2UjR2JaRi5GMzckRjdGLzcmNyQkIitATTQnKSoqRjUkIistIylwbE5GNTckRjwkIisnb1RZaCNGNTckJCIrMHAuTiEqRjVGQTckRkRGPjcmNyQkIisheSFRYGpGNSQhKydvVFloKEY1NyRGSSQhKy0jKXBsJilGNTckJCIra1VLLWFGNUZONyRGUUZLNyY3JCQhK3BVSy1hRjUkISskb1RZaChGNTckRlYkISsqPilwbCYpRjU3JCQhKyZ5IVFgakY1RmVuNyRGaG5GWDcmNyQkISswcC5OISpGNUY+NyRGXW9GQTckJCErQE00JykqKkY1RkE3JEZhb0Y+NyY3JEYsJCIrZSNHYlonRjU3JEYsJCIrVTxaQ2JGNTckRjdGaW83JEY3RmZvNyY3JCQiK3IoUkErJUY1JCErM1BkeVZGNTckRl9wJCErQy1qSGBGNTckJCIrYks9XklGNUZkcDckRmdwRmFwNyY3JCQhK1MzIjNCJkY1JCIrQy1qSEJGNTckRlxxJCIrM1BkeThGNTckJCErY3QnPT0nRjVGYXE3JEZkcUZecTcmNyQkIitjdCc9PSdGNUZecTckRmlxRmFxNyQkIitTMyIzQiZGNUZhcTckRl1yRl5xNyY3JCQhK2VLPV5JRjUkISsyUGR5VkY1NyRGYnIkIStCLWpIYEY1NyQkISt1KFJBKyVGNUZncjckRmpyRmRyLUkmQ09MT1JHRiU2QUkkUkdCR0YlIiIiRmFzJCIiIyEiIkZhc0Zhc0Zic0Zhc0Zhc0Zic0Zhc0Zhc0Zic0Zhc0Zhc0Zic0Zhc0Zhc0Zic0Zhc0Zhc0Zic0Zhc0Zhc0Zic0Zhc0Zhc0Zic0Zhc0Zhc0Zicy1JJlNUWUxFR0YlNiNJLFBBVENITk9HUklER0YlLUklVEVYVEdGJTYkNyQkIiIhRl50JEZhc0ZedFEiMUYoLUZqczYkNyQkIitqXmM1JipGNSQiK1cqcCw0JEY1USIyRigtRmpzNiQ3JCQiK0FEJnkoZUY1JCErVypwLDQpRjVRIjNGKC1GanM2JDckJCErRkQmeShlRjUkIStUKnAsNClGNVEiNEYoLUZqczYkNyQkIStqXmM1JipGNUZmdFEiNUYoLUZqczYkNyRGXXQkIiInRmRzUSI2RigtRmpzNiQ3JCQiKzg6ckVORjUkISttPjVhW0Y1USI3RigtRmpzNiQ3JCQhKyk0UmpxJkY1JCIrbT41YT1GNVEiOEYoLUZqczYkNyQkIispNFJqcSZGNUZid1EiOUYoLUZqczYkNyQkISs7OnJFTkY1JCErbD41YVtGNVEjMTBGKC1GJDYmNyRGXXhGZ3ctRl5zNiZGYHNGXnRGXnRGYXMtSSpUSElDS05FU1NHRiU2I0Zjcy1GZnM2I0klTElORUdGJS1GJDYmNyRGXXhGYXZGZnhGaHhGW3ktRiQ2JjckRl14RmN1RmZ4Rmh4Rlt5LUYkNiY3JEZnd0ZdeEZmeEZoeEZbeS1GJDYmNyRGZ3dGX3dGZnhGaHhGW3ktRiQ2JjckRmd3RmN0RmZ4Rmh4Rlt5LUYkNiY3JEZfd0Znd0ZmeEZoeEZbeS1GJDYmNyRGX3dGZ3ZGZnhGaHhGW3ktRiQ2JjckRl93Rlt2RmZ4Rmh4Rlt5LUYkNiY3JEZndkZfd0ZmeEZoeEZbeS1GJDYmNyRGZ3ZGYXZGZnhGaHhGW3ktRiQ2JjckRmd2Rlt1RmZ4Rmh4Rlt5LUYkNiY3JEZhdkZdeEZmeEZoeEZbeS1GJDYmNyRGYXZGZ3ZGZnhGaHhGW3ktRiQ2JjckRmF2Rlx0RmZ4Rmh4Rlt5LUYkNiY3JEZbdkZfd0ZmeEZoeEZbeS1GJDYmNyRGW3ZGY3VGZnhGaHhGW3ktRiQ2JjckRlt2Rlx0RmZ4Rmh4Rlt5LUYkNiY3JEZjdUZdeEZmeEZoeEZbeS1GJDYmNyRGY3VGW3ZGZnhGaHhGW3ktRiQ2JjckRmN1Rlt1RmZ4Rmh4Rlt5LUYkNiY3JEZbdUZndkZmeEZoeEZbeS1GJDYmNyRGW3VGY3VGZnhGaHhGW3ktRiQ2JjckRlt1RmN0RmZ4Rmh4Rlt5LUYkNiY3JEZjdEZnd0ZmeEZoeEZbeS1GJDYmNyRGY3RGW3VGZnhGaHhGW3ktRiQ2JjckRmN0Rlx0RmZ4Rmh4Rlt5LUYkNiY3JEZcdEZhdkZmeEZoeEZbeS1GJDYmNyRGXHRGW3ZGZnhGaHhGW3ktRiQ2JjckRlx0RmN0RmZ4Rmh4Rlt5LUkoU0NBTElOR0dGKDYjSSxDT05TVFJBSU5FREdGJS1JKkFYRVNTVFlMRUdGJTYjSSVOT05FR0Yl

s := time(): CircularChromaticIndex( Pete ); time()-s;

IyIjNiIiJA==

JCImPHoiISIk

J3 := SpecialGraphs:-FlowerSnark(3): DrawGraph( J3 );

NlUtSSlQT0xZR09OU0c2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYwNyY3JCQiK2woUVMjXCEjNiQiK3dRUyNcIiEjNTckRiwkIitNNydmMiZGLjckJCErbChRUyNcRi5GMzckRjZGLzcmNyQkIishR0glZThGMSQhKU83J2YoRi43JEY7JCErbShRUyMqKkYuNyQkIit0X0BPUEYuRkA3JEZDRj03JjckJCErbl9AT1BGLiQhKVg3J2YoRi43JEZIJCErdihRUyMqKkYuNyQkISshR0glZThGMUZNNyRGUEZKNyY3JEYsJCIrKVFTI1w1ISIqNyRGLCQiK0NoZjImKkYxNyRGNkZZNyRGNkZVNyY3JCQiK3Mqei0jcEYxJCIrMyRbRzopRjE3JEZpbiQiK2MwL29yRjE3JCQiKz1BWk5mRjFGXm83JEZhb0ZbbzcmNyQkIitUIltTLiJGVyQiK2NjKSlHQUYxNyRGZm8kIistejJXN0YxNyQkIithT25iJCpGMUZbcDckRl5wRmhvNyY3JCQiKzl6bF8iKkYxJCErRWhmMlhGMTckRmNwJCEreVFTI1wmRjE3JCQiK2csJnk7KUYxRmhwNyRGW3FGZXA3JjckJCIrL2BnN1JGMSQhK01CXy8qKUYxNyRGYHEkISsnM0kkKikpKkYxNyQkIitfdnpGSEYxRmVxNyRGaHFGYnE3JjckJCErYXZ6RkhGMSQhK0tCXy8qKUYxNyRGXXJGZXE3JCQhKzNgZzdSRjFGZXE3JEZjckZfcjcmNyQkIStjLCZ5OylGMSQhK0toZjJYRjE3JEZociQhKycpUVMjXCZGMTckJCErNXpsXyIqRjFGXXM3JEZgc0ZqcjcmNyQkIStdT25iJCpGMSQiK3VjKSlHQUYxNyRGZXMkIitBejJXN0YxNyQkIStTIltTLiJGV0ZqczckRl10RmdzNyY3JCQhKzVBWk5mRjEkIis7JFtHOilGMTckRmJ0JCIrazAvb3JGMTckJCEraSp6LSNwRjFGZ3Q3JEZqdEZkdC1JJkNPTE9SR0YlNkdJJFJHQkdGJSIiIkZhdSQiIiMhIiJGYXVGYXVGYnVGYXVGYXVGYnVGYXVGYXVGYnVGYXVGYXVGYnVGYXVGYXVGYnVGYXVGYXVGYnVGYXVGYXVGYnVGYXVGYXVGYnVGYXVGYXVGYnVGYXVGYXVGYnVGYXVGYXVGYnUtSSZTVFlMRUdGJTYjSSxQQVRDSE5PR1JJREdGJS1JJVRFWFRHRiU2JDckJCIiIUZediQiKyoqKioqKioqKipGLlEiMUYoLUZqdTYkNyQkIitRU0RnJylGLiQhKywrKytdRi5RIjJGKC1GanU2JDckJCErS1NEZycpRi4kISs1KysrXUYuUSIzRigtRmp1NiQ3JEZddiRGYXVGXnZRIjRGKC1GanU2JDckJCIrJjR3eVUnRjEkIitLV1dnd0YxUSI1RigtRmp1NiQ3JCQiK0l2MlspKkYxJCIrejxbTzxGMVEiNkYoLUZqdTYkNyQkIitQU0RnJylGMSQhKy0rKytdRjFRIjdGKC1GanU2JDckJCIrRzk/P01GMSQhKzVpI3BSKkYxUSI4RigtRmp1NiQ3JCQhK0o5Pz9NRjEkISs0aSNwUipGMVEiOUYoLUZqdTYkNyQkIStMU0RnJylGMSQhKzQrKytdRjFRIzEwRigtRmp1NiQ3JCQhK0V2MlspKkYxJCIrKXoiW088RjFRIzExRigtRmp1NiQ3JCQhKyczd3lVJ0YxJCIrU1dXZ3dGMVEjMTJGKC1GJDYmNyRGYVtsRml6LUZedTYmRmB1Rl52Rl52RmF1LUkqVEhJQ0tORVNTR0YlNiNGY3UtRmZ1NiNJJUxJTkVHRiUtRiQ2JjckRmFbbEZheUZqW2xGXFxsRl9cbC1GJDYmNyRGYVtsRmR3RmpbbEZcXGxGX1xsLUYkNiY3JEZpekZhW2xGaltsRlxcbEZfXGwtRiQ2JjckRml6RmF6RmpbbEZcXGxGX1xsLUYkNiY3JEZpekZheEZqW2xGXFxsRl9cbC1GJDYmNyRGYXpGaXpGaltsRlxcbEZfXGwtRiQ2JjckRmF6Rml5RmpbbEZcXGxGX1xsLUYkNiY3JEZhekZcd0ZqW2xGXFxsRl9cbC1GJDYmNyRGaXlGYXpGaltsRlxcbEZfXGwtRiQ2JjckRml5RmF5RmpbbEZcXGxGX1xsLUYkNiY3JEZpeUZpd0ZqW2xGXFxsRl9cbC1GJDYmNyRGYXlGYVtsRmpbbEZcXGxGX1xsLUYkNiY3JEZheUZpeUZqW2xGXFxsRl9cbC1GJDYmNyRGYXlGaXhGaltsRlxcbEZfXGwtRiQ2JjckRml4RmF5RmpbbEZcXGxGX1xsLUYkNiY3JEZpeEZheEZqW2xGXFxsRl9cbC1GJDYmNyRGaXhGZHZGaltsRlxcbEZfXGwtRiQ2JjckRmF4Rml6RmpbbEZcXGxGX1xsLUYkNiY3JEZheEZpeEZqW2xGXFxsRl9cbC1GJDYmNyRGYXhGaXdGaltsRlxcbEZfXGwtRiQ2JjckRml3Rml5RmpbbEZcXGxGX1xsLUYkNiY3JEZpd0ZheEZqW2xGXFxsRl9cbC1GJDYmNyRGaXdGZHdGaltsRlxcbEZfXGwtRiQ2JjckRmR3RmFbbEZqW2xGXFxsRl9cbC1GJDYmNyRGZHdGaXdGaltsRlxcbEZfXGwtRiQ2JjckRmR3Rlx2RmpbbEZcXGxGX1xsLUYkNiY3JEZcd0ZhekZqW2xGXFxsRl9cbC1GJDYmNyRGXHdGZHZGaltsRlxcbEZfXGwtRiQ2JjckRlx3Rlx2RmpbbEZcXGxGX1xsLUYkNiY3JEZkdkZpeEZqW2xGXFxsRl9cbC1GJDYmNyRGZHZGXHdGaltsRlxcbEZfXGwtRiQ2JjckRmR2Rlx2RmpbbEZcXGxGX1xsLUYkNiY3JEZcdkZkd0ZqW2xGXFxsRl9cbC1GJDYmNyRGXHZGXHdGaltsRlxcbEZfXGwtRiQ2JjckRlx2RmR2RmpbbEZcXGxGX1xsLUkoU0NBTElOR0dGKDYjSSxDT05TVFJBSU5FREdGJS1JKkFYRVNTVFlMRUdGJTYjSSVOT05FR0Yl

s := time(): CircularChromaticIndex( J3 ); time()-s;

Warning, computation interrupted

JCIpVCRwJz0hIiQ=