BEGIN:VCALENDAR
VERSION:2.0
PRODID:-// - ECPv5.3.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://aarms.math.ca
X-WR-CALDESC:Events for 
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20240101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20240925T150000
DTEND;TZID=UTC:20240925T163000
DTSTAMP:20260609T054039
CREATED:20240925T124502Z
LAST-MODIFIED:20240925T124502Z
UID:7696-1727276400-1727281800@aarms.math.ca
SUMMARY:Atlantic Graph Theory Seminar
DESCRIPTION:Recolouring Graphs: Decompositions\, A Dichotomy Theorem and Frozen   Colourings \nSpeaker: Kathie Cameron\, Wilfrid Laurier University \nA k-colouring of a graph G is an assignment of at most k colours to the vertices of a graph so that the ends of each edge of the graph get different colours. We consider the question: When it is possible to obtain any k-colouring from any other by changing the colour of one vertex at a time\, while always having a k-colouring? This question is equivalent to asking whether the “reconfiguration graph” is connected: The reconfiguration graph of the k-colourings\, denoted Rk(G)\, is the graph whose vertices are the k-colourings of G\, and two colourings are adjacent in Rk(G) if they differ in colour on exactly one vertex. We call a graph recolourable if Rk(G) is connected for every k greater than its chromatic number.\n\nWe have characterized the graphs H such that all graphs G which don’t contain H as an induced subgraph are recolourable. We have done the same when two 4-vertex graphs are excluded as induced subgraphs (except for one class) and for some classes of graphs which exclude as an induced subgraph the path on 5 vertices.\n\nDecompositions are important in solving optimization problems on structured classes of graphs. We have shown that modular decomposition and a stronger version of clique cutsets which we call tight clique cutsets can be used to show that certain classes are recolourable.\n\nA k-colouring of a graph is called frozen if there is no vertex whose colour can be changed so that the result is still a k-colouring. A frozen colouring corresponds to an isolated vertex of the reconfiguration graph\, and thus the existence of a frozen colouring is one way to show that a class of graphs is not recolourable. We have found several new classes of graphs with frozen colourings and an operation which transforms a k-chromatic graph with a frozen (k+1)-colouring into a (k+1)-chromatic graph with a frozen (k+2)-colouring.\nThis is joint work with Manoj Belavadi\, Elias Hildred\, Owen Merkel and Dewi Sintiari.\n\n\nZoom link:\nhttps://us02web.zoom.us/j/86861499971?pwd=rTDAaju0TCu24asnaBGvkuNlT11KZ1.1\n\nMeeting ID: 868 6149 9971\nPasscode: 325258
URL:https://aarms.math.ca/event/atlantic-graph-theory-seminar-16/
LOCATION:Online via Zoom
CATEGORIES:AARMS Atlantic Graph Theory Seminar
END:VEVENT
END:VCALENDAR