Title: Some results concerning frozen homomorphisms
| Speaker: | Ben Moore |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
A colouring is frozen if you cannot change any vertices colour and remain a proper colouring. Such colourings appear frequently, for example, they are obstructions to using markov chains to approximately count the number of colourings. They also appear as obstructions to using reconfiguration to prove Hedetnemi's conjecture. I will show some amount of the following two results:
1) If the chromatic number of G is strictly larger than k, then G contains at least (k-1)!/2 cycles of length 0 mod k.
2) Let H be a connected graph. If there exists a graph which admits a frozen H-colouring, and H has at least three vertices, then determining if a graph G has a frozen H-colouring is NP-complete, otherwise it is in P.
Joint work with Rick Brewster, Jon Noel, Mark Siggers, and Jae-Baek Lee.