{"id":3952,"date":"2021-05-05T13:54:29","date_gmt":"2021-05-05T17:54:29","guid":{"rendered":"http:\/\/matroidunion.org\/?p=3952"},"modified":"2021-05-13T16:39:45","modified_gmt":"2021-05-13T20:39:45","slug":"online-talk-sophie-spirkl-2","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=3952","title":{"rendered":"Online Talk: Sophie Spirkl"},"content":{"rendered":"\n<p><strong>Monday, May 10,<\/strong> <strong>3pm ET<\/strong> (8pm BST, 7am Tue NZST)<br \/><strong><a href=\"https:\/\/sites.google.com\/site\/sophiespirkl\/\">Sophie Spirkl<\/a><\/strong>, University of Waterloo<br \/><strong>The complexity of list-5-colouring H-free graphs<\/strong><\/p>\n<div><b>YouTube:\u00a0<\/b><a href=\"https:\/\/youtu.be\/454V6XV4bRY\">https:\/\/youtu.be\/454V6XV4bRY<\/a><\/div>\n<h5>\u00a0<\/h5>\n<h5><b><\/b><strong>Abstract:<\/strong><\/h5>\n<h5>A $k$-list-assignment for a graph $G$ is a function $L$ from $V(G)$ to subsets of $\\{1, \u2026, k\\}$. The list-$k$-colouring problem asks, given $G$ and a $k$-list-assignment $L$, is there a colouring $f$ of $G$ with $f(v)$ in $L(v)$ for all $v$ in $V(G)$? This generalizes the $k$-colouring problem (where we use $L(v) = \\{1, \u2026, k\\}$ for every vertex).<\/h5>\n<h5>\u00a0<\/h5>\n<h5>For $k$ at least $3$, both $k$-colouring and list-$k$-colouring are NP-hard, which motivates studying the complexity of these problems when the input is restricted to $H$-free graphs (for a fixed $H$, excluded as an induced subgraph).<\/h5>\n<h5>\u00a0<\/h5>\n<h5>I will present an algorithm for list-$5$-colouring restricted to $H$-free graphs for all $H$ which consist of connected components each of which is a $3$-vertex path. This, together with previous results, gives a complete answer to the question, \u201cfor which $H$ is list-$5$-colouring restricted to $H$-free graphs NP-hard?\u201d<\/h5>\n<h5>\u00a0<\/h5>\n<h5>Joint work with Sepehr Hajebi and Yanjia Li.<\/h5>\n","protected":false},"excerpt":{"rendered":"<p>Monday, May 10, 3pm ET (8pm BST, 7am Tue NZST)Sophie Spirkl, University of WaterlooThe complexity of list-5-colouring H-free graphs YouTube:\u00a0https:\/\/youtu.be\/454V6XV4bRY \u00a0 Abstract: A $k$-list-assignment for a graph $G$ is a function $L$ from $V(G)$ to subsets of $\\{1, \u2026, k\\}$. &hellip; <a href=\"https:\/\/matroidunion.org\/?p=3952\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":20,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[11],"class_list":["post-3952","post","type-post","status-publish","format-standard","hentry","category-matroids","tag-online-talks"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/3952","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3952"}],"version-history":[{"count":5,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/3952\/revisions"}],"predecessor-version":[{"id":4057,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/3952\/revisions\/4057"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3952"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3952"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3952"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}