DMS Combinatorics Seminar

Speaker: Pete Johnson

Title: A weird list-coloring problem descending from a problem of Hedetniemi, plus:  Another problem I glimpsed at the Southeastern Conference

Abstract for the first part

Steve Hedetniemi asked one day, in the presence of Sarah Holliday, “For which finite simple graphs G does the indexed family of open neighborhoods of vertices in G have a 'system of distinct representatives'?" In other words:

Suppose that G is a finite simple graph on a vertex set V, and let K be the complete graph on V.  Assign to each v in V the “list” L(v)  =  N_G(v).  Under what conditions on G is K properly L-colorable?  An answer to this question was given the last time I gave a talk in this seminar.  Here’s a new question:  Let G, V, and L be as above:  Under what conditions on G is G properly L-colorable?  I’ll give the answer, but no proof.  (I have a proof, and it’s not hard, but it is long.  The result is so meek and mild that there must be a short proof somewhere,  maybe with Erdos, in heaven.)

All of this leads to a graph parameter that I will denote by hh, and the answer alluded to characterizes those graphs G such that hh(G) > 0.  Next problem:  For which G is hh(G) > 1 ?

Dean Hoffman is inviting you to a scheduled Auburn University Zoom e-meeting. If you're a new participant, we have a quick start guide here: https://aub.ie/zoomquickstart

Topic: Spring 2021 - SEMINAR: Combinatorics (MATH-7950-102)

    Every week on Tue, Thu, until Apr 29, 2021

    Weekly: https://auburn.zoom.us/meeting/tZYudumtqjIrGN01qLq63ffXv2rO3T9jMoS0/ics?icsToken=98tyKuGqrToqH9CcsRuORpwQA4j4c-_wiFhcjY0NzQ7JEnYAZAXOILBQHeFLSdL9

Join from PC, Mac, Linux, iOS or Android: https://auburn.zoom.us/j/82310549129

Connect using Computer/Device audio if possible.

Or Telephone: Meeting ID: 823 1054 9129

    Dial: +1 312 626 6799 (US Toll)

        or +1 646 876 9923 (US Toll)

Or an H.323/SIP room system:

    H.323: 162.255.37.11 (US West) or 162.255.36.11 (US East)

    Meeting ID: 823 1054 9129

    SIP: 82310549129@zoomcrc.com