University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Algebraic Graph Theory Seminar - Ben MooreExport this event to calendar

Thursday, May 23, 2019 — 2:30 PM EDT

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. 

Location 
MC - Mathematics & Computer Building
5479
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (136)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)