• Login
    View Item 
    •   SMARTech Home
    • College of Computing (CoC)
    • Algorithms and Randomness Center (ARC)
    • ARC Talks and Events
    • View Item
    •   SMARTech Home
    • College of Computing (CoC)
    • Algorithms and Randomness Center (ARC)
    • ARC Talks and Events
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    The list chromatic number of graphs with small clique number

    Thumbnail
    View/Open
    molloy.mp4 (454.2Mb)
    molloy_videostream.html (985bytes)
    transcription.txt (48.22Kb)
    Date
    2017-10-20
    Author
    Molloy, Mike
    Metadata
    Show full item record
    Abstract
    The Lovasz Local Lemma, a cornerstone of the probabilistic method, is a powerful and widely used proof technique. In 2009, Moser introduced a technique called entropy compression to provide efficient algorithms which construct objects that the Local Lemma guarantees to exist. Recently, entropy compression has been used to develop more powerful versions of the Local Lemma which provide existence proofs in settings where the original Local Lemma does not apply. I will illustrate this technique with applications to graph colouring: (a) colouring triangle-free graphs, and (b) frugal colouring, where no colour can appear too many times in any neighbourhood. We prove that every triangle-free graph with maximum degree $\D$ has list chromatic number at most $(1+o(1))\frac{\D}{\ln \D}$. This matches the best-known bound for graphs of girth at least 5. We also provide a new proof that for any $r\geq4$ every $K_r$-free graph has list-chromatic number at most $200r\frac{\D\ln\ln\D}{\ln\D}$.
    URI
    http://hdl.handle.net/1853/58856
    Collections
    • ARC Talks and Events [88]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology