Sophie Spirkl

activity

20182022

P_{6}

-free graphs. II. Finding an excellent precoloring

12 citations · 26 across the 7 of their papers we have counts for

collaborators

Showing 2018Show all

3 papers · 1 filter

cs.DM2018★ 2 cited

$H$ -colouring $P_{t}$ -free graphs in subexponential time

Carla Groenland, Karolina Okrasa, Pawel Rzążewski +3

A graph is called $P_{t}$ -free if it does not contain the path on $t$ vertices as an induced subgraph. Let $H$ be a multigraph with the property that any two distinct vertices share…

math.CO2018★ 12 cited

Four-coloring $P_{6}$ -free graphs. II. Finding an excellent precoloring

Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong

This is the second paper in a series of two. The goal of the series is to give a polynomial time algorithm for the $4$ -coloring problem and the $4$ -precoloring extension problem re…

math.CO2018★ 3 cited

Four-coloring $P_{6}$ -free graphs. I. Extending an excellent precoloring

Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong

This is the first paper in a series whose goal is to give a polynomial time algorithm for the $4$ -coloring problem and the $4$ -precoloring extension problem restricted to the class…

H-colouring Pt​-free graphs in subexponential time

Four-coloring P6​-free graphs. II. Finding an excellent precoloring

Four-coloring P6​-free graphs. I. Extending an excellent precoloring

$H$ -colouring $P_{t}$ -free graphs in subexponential time

Four-coloring $P_{6}$ -free graphs. II. Finding an excellent precoloring

Four-coloring $P_{6}$ -free graphs. I. Extending an excellent precoloring