Colouring (Pr + Ps)-Free Graphs
Tereza Klimošová, Josef Malík, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Veronika Slívová
Abstract
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)\subseteq \{1,\ldots ,k\},$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo>(</mml:mo> <mml:mi>u</mml:mi> <mml:mo>)</mml:mo> <mml:mo>⊆</mml:mo> <mml:mo>{</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>}</mml:mo> <mml:mo>,</mml:mo> </mml:mrow> </mml:math> 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 $$P_r+P_s$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>r</mml:mi> </mml:msub> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>s</mml:mi> </mml:msub> </mml:mrow> </mml:math> is the disjoint union of the r -vertex path $$P_r$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>r</mml:mi> </mml:msub> </mml:math> and the s -vertex path $$P_s.$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>s</mml:mi> </mml:msub> <mml:mo>.</mml:mo> </mml:mrow> </mml:math> We prove that List 3-Colouring is polynomial-time solvable for $$(P_2+P_5)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>P</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>P</mml:mi> <mml:mn>5</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -free graphs and for $$(P_3+P_4)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>P</mml:mi> <mml:mn>3</mml:mn> </mml:msub> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>P</mml:mi> <mml:mn>4</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -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.