Department of
Applied
Mathematics

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á)