4 citations · 8 across the 3 of their papers we have counts for
9 papers
List-three-coloring -free graphs with no induced 1-subdivision of
Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong
Let and be positive integers. We use to denote the path with vertices and to denote the complete bipartite graph with parts of size and respecti…
Finding an induced path that is not a shortest path
Eli Berger, Paul Seymour, Sophie Spirkl
We give a polynomial-time algorithm that, with input a graph and two vertices of , decides whether there is an induced -path that is longer than the shortest -…
Finding large -colorable subgraphs in hereditary graph classes
Maria Chudnovsky, Jason King, Michał Pilipczuk +2
We study the \textsc{Max Partial -Coloring} problem: given a graph , find the largest induced subgraph of that admits a homomorphism into , where is a fixed patter…
A Deletion-Contraction Relation for the Chromatic Symmetric Function
Logan Crew, Sophie Spirkl
We extend the definition of the chromatic symmetric function to include graphs with a vertex-weight function . We show how this provides…
Entropic matroids and their representation
Emmanuel Abbe, Sophie Spirkl
This paper investigates entropic matroids, that is, matroids whose rank function is given as the Shannon entropy of random variables. In particular, we consider -entropic matroi…
Disproportionate division
Logan Crew, Bhargav Narayanan, Sophie Spirkl
We study the disproportionate version of the classical cake-cutting problem: how efficiently can we divide a cake, here , among agents with different demands $α_1, α_2,…