Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | future lectures)

On 06.12.2018 at 13:20 in S6, there is the following noon lecture:

Colouring (P_r+P_s)-Free Graphs

Tomáš Masařík

KAM MFF, Charles University

Abstract

The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list L(u) ⊆ {1, . . . , k}, then we obtain the List k-Colouring problem. A graph G is H-free if G does not contain H as an induced subgraph. We continue an extensive study into the complexity of these two problems for H-free graphs. The graph Pr+Ps is the disjoint union of the r-vertex path Pr and the s-vertex path Ps. We prove that List 3-Colouring is polynomial-time solvable for (P2+P5)-free graphs and for (P3+P4)-free graphs. Combining our results with known results yields complete complexity classifications of 3-Colouring and List 3-Colouring on H-free graphs for all graphs H up to seven vertices.

In the talk I show you properties of a common supper class, (P3+P5)-free graphs, and some steps of branching that leads eventually to a polynomial number of instances of 2-List Coloring problem, and thus prove the promised theorem.

(joint work with T. Klimošová, J. Malík, J. Novotná, D. Paulusma, V. Slívová)

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010