Maria Chudnovsky

ORCID

Publication Activity (10 Years)

Years Active: 2002-2024
Publications (10 Years): 118

Top Venues

J. Comb. Theory, Ser. B

CoRR

J. Graph Theory

Eur. J. Comb.

Publications

Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, Paul D. Seymour
Induced Subgraphs of Bounded Treewidth and the Container Method. SIAM J. Comput. 53 (3) (2024)
Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong
Four-Coloring $\boldsymbol{P_6}$-Free Graphs. II. Finding an Excellent Precoloring. SIAM J. Comput. 53 (1) (2024)
Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Sepehr Hajebi, Pawel Rzazewski, Sophie Spirkl, Kristina Vuskovic
Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree. J. Comb. Theory, Ser. B 164 (2024)
Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\boldsymbol{H}$-Free Graphs. SIAM J. Comput. 53 (1) (2024)
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl
-free graphs. J. Comb. Theory, Ser. B 164 (2024)
Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov, Sophie Spirkl
Tree Independence Number IV. Even-hole-free Graphs. CoRR (2024)
Tara Abrishami, Eli Berger, Maria Chudnovsky, Shira Zerbib
Graphs with no even holes and no sector wheels are the union of two chordal graphs. Eur. J. Comb. 122 (2024)
Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen, Nicolas Trotignon, Sebastian Wiederrecht
Unavoidable induced subgraphs in graphs with complete bipartite induced minors. CoRR (2024)
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl, Kristina Vuskovic
Induced subgraphs and tree decompositions V. one neighbor in a hole. J. Graph Theory 105 (4) (2024)
Maria Chudnovsky, Sergey Norin, Paul D. Seymour, Jérémie Turcotte
Cops and Robbers on $\boldsymbol{P_5}$-Free Graphs. SIAM J. Discret. Math. 38 (1) (2024)
Maria Chudnovsky, Alex D. Scott, Paul D. Seymour, Sophie Spirkl
Pure pairs. X. Tournaments and the strong Erdős-Hajnal property. Eur. J. Comb. 115 (2024)
Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong
Four-Coloring $P_6$-Free Graphs. I. Extending an Excellent Precoloring. SIAM J. Comput. 53 (1) (2024)
Maria Chudnovsky, Alex D. Scott, Paul D. Seymour, Sophie Spirkl
minor. J. Comb. Theory, Ser. B 164 (2024)
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski
Max Weight Independent Set in Sparse Graphs with No Long Claws. STACS (2024)
Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski
-free graphs. SODA (2024)
Maria Chudnovsky, Ian M. J. McInnis
Characterizing and generalizing cycle completable graphs. Discret. Math. 347 (2) (2024)
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski
Max Weight Independent Set in sparse graphs with no long claws. CoRR (2023)
Maria Chudnovsky, Eran Nevo
Stable sets in flag spheres. Eur. J. Comb. 110 (2023)
Maria Chudnovsky, Shenwei Huang, Pawel Rzazewski, Sophie Spirkl, Mingxian Zhong
-coloring in hereditary classes of graphs. Inf. Comput. 292 (2023)
Maria Chudnovsky, Paul D. Seymour
Proof of a conjecture of Plummer and Zha. J. Graph Theory 103 (3) (2023)
Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl
Induced Subgraphs and Tree Decompositions IV. (Even Hole, Diamond, Pyramid)-Free Graphs. Electron. J. Comb. 30 (2) (2023)
Maria Chudnovsky, Paul D. Seymour
Even-hole-free graphs still have bisimplicial vertices. J. Comb. Theory, Ser. B 161 (2023)
Maria Chudnovsky, Alex D. Scott, Paul D. Seymour, Sophie Spirkl
Polynomial bounds for chromatic number VI. Adding a four-vertex path. Eur. J. Comb. 110 (2023)
Maria Chudnovsky, Alex D. Scott, Paul D. Seymour, Sophie Spirkl
Polynomial bounds for chromatic number VII. Disjoint holes. J. Graph Theory 104 (3) (2023)
Ron Aharoni, Eli Berger, Maria Chudnovsky, He Guo, Shira Zerbib
Nonuniform Degrees and Rainbow Versions of the Caccetta-Häggkvist Conjecture. SIAM J. Discret. Math. 37 (3) (2023)
Maria Chudnovsky, Alex D. Scott, Paul D. Seymour, Sophie Spirkl
Strengthening Rödl's theorem. J. Comb. Theory, Ser. B 163 (2023)
Maria Chudnovsky, Linda Cook, James Davies, Sang-il Oum
Reuniting χ-boundedness with polynomial χ-boundedness. CoRR (2023)
Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski
Sparse induced subgraphs in P_6-free graphs. CoRR (2023)
Maria Chudnovsky, Sergey Norin, Paul D. Seymour, Jérémie Turcotte
-free graphs. CoRR (2023)
Maria Chudnovsky, Patrick Hompe, Alex Scott, Paul D. Seymour, Sophie Spirkl
Concatenating Bipartite Graphs. Electron. J. Comb. 29 (2) (2022)
Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Stéphan Thomassé, Nicolas Trotignon, Kristina Vuskovic
Graphs with polynomially many minimal separators. J. Comb. Theory, Ser. B 152 (2022)
Ron Aharoni, Eli Berger, Maria Chudnovsky, Shira Zerbib
Rainbow Paths and Large Rainbow Matchings. Electron. J. Comb. 29 (1) (2022)
Eli Berger, Krzysztof Choromanski, Maria Chudnovsky, Shira Zerbib
Tournaments and the strong Erdős-Hajnal Property. Eur. J. Comb. 100 (2022)
Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Pawel Rzazewski
Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws. SODA (2022)
Maria Chudnovsky, Neeldhara Misra, Daniël Paulusma, Oliver Schaudt, Akanksha Agrawal
Vertex Partitioning in Graphs: From Structure to Algorithms (Dagstuhl Seminar 22481). Dagstuhl Reports 12 (11) (2022)
Jesse Beisegel, Maria Chudnovsky, Vladimir Gurvich, Martin Milanic, Mary Servatius
Avoidable vertices and edges in graphs: Existence, characterization, and applications. Discret. Appl. Math. 309 (2022)
Tara Abrishami, Maria Chudnovsky, Kristina Vuskovic
Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree. J. Comb. Theory, Ser. B 157 (2022)
Maria Chudnovsky, Adam Kabela, Binlong Li, Petr Vrána
Forbidden Induced Pairs for Perfectness and $\omega$-Colourability of Graphs. Electron. J. Comb. 29 (2) (2022)
Maria Chudnovsky, Shenwei Huang, T. Karthick, Jenny Kaufmann
Square-Free Graphs with no Induced Fork. Electron. J. Comb. 28 (2) (2021)
Maria Chudnovsky, Alex Scott, Paul D. Seymour
Finding a Shortest Odd Hole. ACM Trans. Algorithms 17 (2) (2021)
Maria Chudnovsky, Paul D. Seymour
Erdős-Hajnal for cap-free graphs. J. Comb. Theory, Ser. B 151 (2021)
Maria Chudnovsky, Shenwei Huang, Sophie Spirkl, Mingxian Zhong
. Algorithmica 83 (1) (2021)
Maria Chudnovsky, Cemil Dibek
Strongly perfect claw-free graphs - A short proof. J. Graph Theory 97 (3) (2021)
Flavia Bonomo-Braberman, Maria Chudnovsky, Jan Goedgebeur, Peter Maceli, Oliver Schaudt, Maya Stein, Mingxian Zhong
Better 3-coloring algorithms: Excluding a triangle and a seven vertex path. Theor. Comput. Sci. 850 (2021)
Maria Chudnovsky, Jason King, Michal Pilipczuk, Pawel Rzazewski, Sophie Spirkl
Finding Large H-Colorable Subgraphs in Hereditary Graph Classes. SIAM J. Discret. Math. 35 (4) (2021)
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, Paul D. Seymour
Induced subgraphs of bounded treewidth and the container method. SODA (2021)
Maria Chudnovsky, Cemil Dibek, Paul D. Seymour
New examples of minimal non-strongly-perfect graphs. Discret. Math. 344 (5) (2021)
Maria Chudnovsky, Alex Scott, Paul D. Seymour, Sophie Spirkl
A note on simplicial cliques. Discret. Math. 344 (9) (2021)
Maria Chudnovsky, Alex Scott, Paul D. Seymour
Detecting a Long Odd Hole. Comb. 41 (1) (2021)
Maria Chudnovsky, Alex D. Scott, Paul D. Seymour, Sophie Spirkl
Pure Pairs. II. Excluding All Subdivisions of A Graph. Comb. 41 (3) (2021)
Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Pawel Rzazewski
Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws. CoRR (2021)
Maria Chudnovsky, Alex Scott, Paul D. Seymour
Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings. J. Comb. Theory, Ser. B 150 (2021)
Maria Chudnovsky, Linda Cook, Paul D. Seymour
Excluding the fork and antifork. Discret. Math. 343 (5) (2020)
Maria Chudnovsky, Jason King, Michal Pilipczuk, Pawel Rzazewski, Sophie Spirkl
Finding large $H$-colorable subgraphs in hereditary graph classes. CoRR (2020)
Louigi Addario-Berry, Maria Chudnovsky, Frédéric Havet, Bruce A. Reed, Paul D. Seymour
Corrigendum to "Bisimplicial vertices in even-hole-free graphs". J. Comb. Theory, Ser. B 142 (2020)
Ron Aharoni, Eli Berger, Maria Chudnovsky, Frédéric Havet, Zilin Jiang
Cooperative Colorings of Trees and of Bipartite Graphs. Electron. J. Comb. 27 (1) (2020)
Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé
On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five. SIAM J. Discret. Math. 34 (2) (2020)
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, Paul D. Seymour
Induced subgraphs of bounded treewidth and the container method. CoRR (2020)
Maria Chudnovsky, Eran Nevo
Induced equators in flag spheres. J. Comb. Theory, Ser. A 176 (2020)
Maria Chudnovsky, Jacob Fox, Alex Scott, Paul D. Seymour, Sophie Spirkl
Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs. J. Graph Theory 95 (3) (2020)
Maria Chudnovsky, Alex Scott, Paul D. Seymour, Sophie Spirkl
Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes. J. Comb. Theory, Ser. B 140 (2020)
Maria Chudnovsky, Jason King, Michal Pilipczuk, Pawel Rzazewski, Sophie Spirkl
Finding Large H-Colorable Subgraphs in Hereditary Graph Classes. ESA (2020)
Maria Chudnovsky, Karthick Thiyagarajan, Peter Maceli, Frédéric Maffray
Coloring graphs with no induced five-vertex path or gem. J. Graph Theory 95 (4) (2020)
Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé
-free graphs. SODA (2020)
Maria Chudnovsky, Shenwei Huang, Pawel Rzazewski, Sophie Spirkl, Mingxian Zhong
-coloring in hereditary classes of graphs. CoRR (2020)
Maria Chudnovsky, Alex Scott, Paul D. Seymour, Sophie Spirkl
Detecting an Odd Hole. J. ACM 67 (1) (2020)
Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong
List 3-coloring Pt-free graphs with no induced 1-subdivision of K1, s. Discret. Math. 343 (11) (2020)
Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong
Obstructions for three-coloring graphs without induced paths on six vertices. J. Comb. Theory, Ser. B 140 (2020)
Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong
Obstructions for Three-Coloring and List Three-Coloring H-Free Graphs. SIAM J. Discret. Math. 34 (1) (2020)
Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong
. CoRR (2020)
Ron Aharoni, Eli Berger, Maria Chudnovsky, David M. Howard, Paul D. Seymour
Large rainbow matchings in general graphs. Eur. J. Comb. 79 (2019)
Maria Chudnovsky, Oliver Schaudt, Sophie Spirkl, Maya Stein, Mingxian Zhong
Approximately Coloring Graphs Without Long Induced Paths. Algorithmica 81 (8) (2019)
Maria Chudnovsky, Chun-Hung Liu, Oliver Schaudt, Sophie Spirkl, Nicolas Trotignon, Kristina Vuskovic
Triangle-free graphs that do not contain an induced subdivision of K4 are 3-colorable. J. Graph Theory 92 (2) (2019)
Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. CoRR (2019)
Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon, Kristina Vuskovic
Maximum independent sets in (pyramid, even hole)-free graphs. CoRR (2019)
Jesse Beisegel, Maria Chudnovsky, Vladimir Gurvich, Martin Milanic, Mary Servatius
Avoidable Vertices and Edges in Graphs. CoRR (2019)
Maria Chudnovsky, Vaidy Sivaraman
Perfect divisibility and 2-divisibility. J. Graph Theory 90 (1) (2019)
Eli Berger, Krzysztof Choromanski, Maria Chudnovsky
On the Erdős-Hajnal conjecture for six-vertex tournaments. Eur. J. Comb. 75 (2019)
Maria Chudnovsky, Shenwei Huang, Pawel Rzazewski, Sophie Spirkl, Mingxian Zhong
-Coloring in Hereditary Classes of Graphs. ESA (2019)
Jesse Beisegel, Maria Chudnovsky, Vladimir Gurvich, Martin Milanic, Mary Servatius
Avoidable Vertices and Edges in Graphs. WADS (2019)
Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé
On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five. CoRR (2019)
Maria Chudnovsky, Daniël Paulusma, Oliver Schaudt
Graph Colouring: from Structure to Algorithms (Dagstuhl Seminar 19271). Dagstuhl Reports 9 (6) (2019)
Maria Chudnovsky, Alex Scott, Paul D. Seymour
Induced subgraphs of graphs with large chromatic number. XI. Orientations. Eur. J. Comb. 76 (2019)
Maria Chudnovsky, Irene Lo, Frédéric Maffray, Nicolas Trotignon, Kristina Vuskovic
Coloring square-free Berge graphs. J. Comb. Theory, Ser. B 135 (2019)
Sophie Spirkl, Maria Chudnovsky, Mingxian Zhong
Four-coloring P6-free graphs. SODA (2019)
Maria Chudnovsky, Jacob Fox, Alex D. Scott, Paul D. Seymour, Sophie Spirkl
Towards Erdős-Hajnal for Graphs with No 5-Hole. Comb. 39 (5) (2019)
Maria Chudnovsky, Alex Scott, Paul D. Seymour
Induced subgraphs of graphs with large chromatic number. XII. Distant stars. J. Graph Theory 92 (3) (2019)
Maria Chudnovsky, Alex Scott, Paul D. Seymour
Disjoint paths in unions of tournaments. J. Comb. Theory, Ser. B 135 (2019)
Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong
-free graphs. I. Extending an excellent precoloring. CoRR (2018)
Maria Chudnovsky, Frédéric Maffray, Paul D. Seymour, Sophie Spirkl
Even pairs and prism corners in square-free Berge graphs. J. Comb. Theory, Ser. B 131 (2018)
Maria Chudnovsky
A short proof of the wonderful lemma. J. Graph Theory 87 (3) (2018)
Maria Chudnovsky, Sophie Spirkl, Shira Zerbib
Piercing Axis-Parallel Boxes. Electron. J. Comb. 25 (1) (2018)
Flavia Bonomo, Maria Chudnovsky, Peter Maceli, Oliver Schaudt, Maya Stein, Mingxian Zhong
Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices. Comb. 38 (4) (2018)
Maria Chudnovsky, Ringi Kim, Chun-Hung Liu, Paul D. Seymour, Stéphan Thomassé
Domination in tournaments. J. Comb. Theory, Ser. B 130 (2018)
Maria Chudnovsky, Frédéric Maffray, Paul D. Seymour, Sophie Spirkl
Corrigendum to "Even pairs and prism corners in square-free Berge graphs" [J. Combin. Theory, Ser. B 131 (2018) 12-39]. J. Comb. Theory, Ser. B 133 (2018)
Maria Chudnovsky, Celina M. H. de Figueiredo, Sophie Spirkl
The Sandwich Problem for Decompositions and Almost Monotone Properties. Algorithmica 80 (12) (2018)
Maria Chudnovsky, Juraj Stacho
-Free Graphs. SIAM J. Discret. Math. 32 (2) (2018)
Maria Chudnovsky, Karthick Thiyagarajan, Peter Maceli, Frédéric Maffray
Coloring graphs with no induced five-vertex path or gem. CoRR (2018)
Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong
-free graphs. II. Finding an excellent precoloring. CoRR (2018)
Maria Chudnovsky, Vaidy Sivaraman
Odd Holes in Bull-Free Graphs. SIAM J. Discret. Math. 32 (2) (2018)

Maria Chudnovsky.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Maria Chudnovsky