M. Chudnovsky

activity

20022024

χ

-Boundedness

29 citations · 334 across the 88 of their papers we have counts for

collaborators

Showing 2020 · cs.DSShow all

3 papers · 2 filters

cs.DS2020★ 2 cited

Complexity of $C_{k}$ -coloring in hereditary classes of graphs

Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski +2

For a graph $F$ , a graph $G$ is \emph{ $F$ -free} if it does not contain an induced subgraph isomorphic to $F$ . For two graphs $G$ and $H$ , an \emph{ $H$ -coloring} of $G$ is a mapping…

cs.DS2020

Finding large $H$ -colorable subgraphs in hereditary graph classes

Maria Chudnovsky, Jason King, Michał Pilipczuk +2

We study the \textsc{Max Partial $H$ -Coloring} problem: given a graph $G$ , find the largest induced subgraph of $G$ that admits a homomorphism into $H$ , where $H$ is a fixed patter…

cs.DS2020

Induced subgraphs of bounded treewidth and the container method

Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk +2

A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By $P_{t}$ we denote a path on $t$ vertices. In this paper we give polynomial-…

Complexity of Ck​-coloring in hereditary classes of graphs

Finding large H-colorable subgraphs in hereditary graph classes

Induced subgraphs of bounded treewidth and the container method

Complexity of $C_{k}$ -coloring in hereditary classes of graphs

Finding large $H$ -colorable subgraphs in hereditary graph classes