# Maria Chudnovsky

Mathematician and engineer

## Maria Chudnovsky's AcademicInfluence.com Rankings

## Download Badge

Mathematics Engineering

## Maria Chudnovsky's Degrees

- PhD Mathematics Princeton University
- Bachelors Mathematics University of Buenos Aires

## Similar Degrees You Can Earn

## Why Is Maria Chudnovsky Influential?

(Suggest an Edit or Addition)According to Wikipedia, Maria Chudnovsky is an Israeli-American mathematician working on graph theory and combinatorial optimization. She is a 2012 MacArthur Fellow. Education and career Chudnovsky is a professor in the department of mathematics at Princeton University. She grew up in Russia and Israel, studying at the Technion, and received her Ph.D. in 2003 from Princeton University under the supervision of Paul Seymour. After postdoctoral research at the Clay Mathematics Institute, she became an assistant professor at Princeton University in 2005, and moved to Columbia University in 2006. By 2014, she was the Liu Family Professor of Industrial Engineering and Operations Research at Columbia. She returned to Princeton as a professor of mathematics in 2015.

## Maria Chudnovsky's Published Works

### Published Works

- The Strong Perfect Graph Theorem (2002) (598)
- Recognizing Berge Graphs (2005) (311)
- The structure of claw-free graphs (2005) (206)
- The roots of the independence polynomial of a clawfree graph (2007) (185)
- Claw-free graphs. V. Global structure (2008) (104)
- The Erdös–Hajnal Conjecture—A Survey (2014) (91)
- Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices (2018) (79)
- Claw-free graphs. IV. Decomposition theorem (2008) (71)
- Packing Non-Zero A-Paths In Group-Labelled Graphs (2006) (69)
- The three-in-a-tree problem (2010) (66)
- Bisimplicial vertices in even-hole-free graphs (2008) (62)
- The Erdös-Hajnal conjecture for bull-free graphs (2008) (60)
- Excluding induced subgraphs (2006) (59)
- Progress on perfect graphs (2003) (57)
- Claw-free graphs. III. Circular interval graphs (2008) (56)
- Tournaments and colouring (2012) (53)
- Detecting even holes (2005) (51)
- Claw-free graphs. I. Orientable prismatic graphs (2007) (48)
- A well-quasi-order for tournaments (2011) (45)
- Claw-free graphs. II. Non-orientable prismatic graphs (2008) (44)
- The structure of bull-free graphs II and III - A summary (2012) (42)
- Berge trigraphs (2006) (42)
- K4-free graphs with no odd holes (2010) (39)
- Claw-free graphs VI. Colouring (2010) (39)
- Analyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theory (2012) (39)
- Induced Subgraphs of Graphs with Large Chromatic Number. III. Long Holes (2015) (39)
- Cycles in dense digraphs (2007) (38)
- The structure of bull-free graphs I - Three-edge-paths with centers and anticenters (2012) (36)
- Four-coloring P6-free graphs (2019) (35)
- An algorithm for packing non-zero A-paths in group-labelled graphs (2008) (34)
- Substitution and χ-boundedness (2013) (34)
- Detecting a Theta or a Prism (2008) (34)
- The edge-density for K2, t minors (2011) (34)
- Claw-free graphs. VII. Quasi-line graphs (2012) (32)
- Tournament immersion and cutwidth (2012) (32)
- A counterexample to a conjecture of Schwartz (2013) (32)
- Forcing large transitive subtournaments (2015) (31)
- Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes (2017) (31)
- Berge trigraphs and their applications (2003) (30)
- Induced subgraphs of graphs with large chromatic number. XII. Distant stars (2017) (29)
- Perfect matchings in planar cubic graphs (2012) (28)
- Disjoint paths in tournaments (2014) (28)
- Coloring quasi‐line graphs (2007) (26)
- Triangulated Spheres and Colored Cliques (2002) (25)
- Coloring graphs with forbidden induced subgraphs (2014) (25)
- Pure pairs. I. Trees and linear anticomplete pairs (2018) (24)
- Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs (2008) (24)
- Large rainbow matchings in general graphs (2016) (24)
- Even pairs in Berge graphs (2009) (24)
- Perfect divisibility and 2‐divisibility (2017) (24)
- Hadwiger's conjecture for quasi‐line graphs (2008) (23)
- Coloring perfect graphs with no balanced skew-partitions (2013) (23)
- A De Bruijn-Erdős Theorem for Chordal Graphs (2012) (23)
- Induced subgraphs of bounded treewidth and the container method (2020) (22)
- Extending the Gyárfás-Sumner conjecture (2014) (22)
- Detecting an Odd Hole (2019) (22)
- Large cliques or stable sets in graphs with no four‐edge path and no five‐edge path in the complement (2012) (22)
- Obstructions for three-coloring graphs with one forbidden induced subgraph (2016) (21)
- Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs (2019) (21)
- Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs (2009) (21)
- Edge-colouring eight-regular planar graphs (2012) (20)
- Coloring graphs with no induced five‐vertex path or gem (2018) (20)
- 4‐Coloring P6‐Free Graphs with No Induced 5‐Cycles (2014) (20)
- Excluding paths and antipaths (2015) (19)
- On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five (2019) (19)
- Packing seagulls (2012) (18)
- Lines in hypergraphs (2011) (18)
- Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures (2014) (17)
- Rao's degree sequence conjecture (2014) (17)
- Towards Erdős-Hajnal for Graphs with No 5-Hole (2018) (17)
- The edge-density for K 2 , t minors (2008) (17)
- Three-coloring graphs with no induced seven-vertex path I : the triangle-free case (2014) (16)
- Coloring quasi-line graphs (2007) (16)
- Three-coloring graphs with no induced seven-vertex path II : using a triangle (2015) (16)
- Obstructions for three-coloring graphs without induced paths on six vertices (2015) (15)
- Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings (2016) (15)
- Four-coloring Ps6-free graphs. I. Extending an excellent precoloring (2018) (15)
- Tournaments with near-linear transitive subsets (2014) (15)
- Unavoidable induced subgraphs in large graphs with no homogeneous sets (2015) (14)
- Induced subgraphs of graphs with large chromatic number. XI. Orientations (2017) (14)
- Four-coloring P6-free graphs. II. Finding an excellent precoloring (2018) (14)
- On the Erdős-Hajnal conjecture for six-vertex tournaments (2019) (14)
- Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree (2021) (13)
- Proof of the Kalai-Meshulam conjecture (2018) (13)
- Fair representation by independent sets (2016) (12)
- A Local Strengthening of Reed's Omega, Delta, Chi Conjecture for Quasi-line Graphs (2011) (12)
- Edge-colouring seven-regular planar graphs (2012) (12)
- Trees and linear anticomplete pairs (2018) (12)
- Avoidable Vertices and Edges in Graphs (2019) (11)
- Growing Without Cloning (2012) (11)
- Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree (2020) (11)
- Decomposing and Clique‐Coloring (Diamond, Odd‐Hole)‐Free Graphs (2017) (11)
- Pure Pairs. II. Excluding All Subdivisions of A Graph (2020) (11)
- Even-hole-free graphs still have bisimplicial vertices (2019) (11)
- An approximate version of Hadwiger's conjecture for claw‐free graphs (2010) (11)
- Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth (2021) (11)
- Detecting an induced net subdivision (2013) (10)
- Partial characterizations of clique-perfect graphs (2005) (10)
- The Structure of Claw‐Free Perfect Graphs (2014) (10)
- Piercing Axis-Parallel Boxes (2017) (10)
- Excluding pairs of graphs (2013) (10)
- 3-Colorable Subclasses of P8-Free Graphs (2018) (10)
- Triangle‐free graphs that do not contain an induced subdivision of K4 are 3‐colorable (2017) (9)
- The structure of bull-free graphs III — global structure (2011) (9)
- Odd holes in bull-free graphs (2017) (9)
- Sparse graphs without linear anticomplete pairs (2018) (9)
- Claw-free Graphs VI. Colouring Claw-free Graphs (2009) (9)
- Finding large $H$-colorable subgraphs in hereditary graph classes (2020) (9)
- List-three-coloring graphs with no induced $P_6+rP_3$. (2018) (9)
- Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs (2022) (8)
- List 3-Coloring Graphs with No Induced P6+rP3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_6+rP_3$$\end{document} (2020) (8)
- List 3-coloring Pt-free graphs with no induced 1-subdivision of K1, s (2020) (8)
- Disjoint paths in unions of tournaments (2016) (8)
- Excluding Induced Subdivisions of the Bull and Related Graphs (2012) (8)
- An approximate version of Hadwiger's conjecture for claw-free graphs (2010) (8)
- Immersion in four-edge-connected graphs (2013) (8)
- Colouring graphs with no long holes (2015) (8)
- Analyzing the performance of greedy maximal scheduling via local pooling and graph theory (2010) (8)
- Vertex-minors and the Erdős-Hajnal conjecture (2018) (7)
- Colouring perfect graphs with bounded clique number (2017) (7)
- Optimal antithickenings of claw-free trigraphs (2011) (7)
- Simplicial Vertices in Graphs with no Induced Four‐Edge Path or Four‐Edge Antipath, and the H6‐Conjecture (2013) (7)
- Obstructions for three-coloring and list three-coloring H-free graphs (2017) (7)
- Complexity of Ck-Coloring in Hereditary Classes of Graphs (2019) (7)
- Wheel-free planar graphs (2013) (6)
- Finding a Shortest Odd Hole (2020) (6)
- Testing for a theta (2007) (6)
- Detecting a Long Odd Hole (2019) (6)
- Domination in tournaments (2017) (6)
- Finding Large H-Colorable Subgraphs in Hereditary Graph Classes (2021) (6)
- Claw-free graphs with strongly perfect complements. Fractional and integral version. Part I. Basic graphs (2011) (6)
- Three-colourable perfect graphs without even pairs (2012) (6)
- Excluding four-edge paths and their complements (2013) (6)
- Maximum independent sets in (pyramid, even hole)-free graphs (2019) (6)
- quasi-line graphs (2011) (6)
- Pure pairs. III. Sparse graphs with no polynomial‐sized anticomplete pairs (2018) (6)
- Induced subgraphs and tree decompositions V. One neighbor in a hole (2022) (5)
- Pure pairs. VIII. Excluding a sparse graph (2022) (5)
- Square-Free Graphs with no Induced Fork (2021) (5)
- Coloring square-free Berge graphs (2015) (5)
- Triangle-free graphs with no six-vertex induced path (2018) (5)
- Forbidden structures and algorithms in graphs and digraphs (2011) (5)
- Bipartite minors (2013) (5)
- Proof of a conjecture of Plummer and Zha (2022) (5)
- The Structure of Bull‐Free Perfect Graphs (2013) (4)
- Graphs with polynomially many minimal separators (2020) (4)
- On the Erdös-Lovász Tihany Conjecture for Claw-Free Graphs (2013) (4)
- Approximately Coloring Graphs Without Long Induced Paths (2016) (4)
- Hadwiger's conjecture for quasi-line graphs (2008) (4)
- Cliques in the union of graphs (2015) (4)
- Excluding the fork and antifork (2020) (4)
- Cooperative Colorings of Trees and of Bipartite Graphs (2018) (4)
- Hadwiger's conjecture and seagull packing (2010) (4)
- Strengthening Rodl's theorem (2021) (4)
- Induced equators in flag spheres (2019) (4)
- Graphs with No Induced Five‐Vertex Path or Antipath (2014) (4)
- Even-hole-free graphs with bounded degree have bounded treewidth (2020) (4)
- Non-uniform degrees and rainbow versions of the Caccetta-H\"aggkvist conjecture (2021) (4)
- Polynomial bounds for chromatic number VI. Adding a four-vertex path (2022) (4)
- The structure of bull-free graphs II — elementary trigraphs (2011) (4)
- Tournaments and the strong Erdős–Hajnal Property (2020) (4)
- Induced subgraphs and tree-decompositions VII. Basic obstructions in $H$-free graphs (2022) (4)
- List-three-coloring Pt-free graphs with no induced 1-subdivision of K1, s (2020) (3)
- Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws (2021) (3)
- Induced subgraphs and tree decompositions VIII. Excluding a forest in (theta, prism)-free graphs (2023) (3)
- Subdivided Claws and the Clique-Stable Set Separation Property (2019) (3)
- Solution of three problems of Cornuéjols (2008) (3)
- Better 3-coloring algorithms: Excluding a triangle and a seven vertex path (2014) (3)
- Submodular functions and perfect graphs (2021) (3)
- Disjoint dijoins (2014) (3)
- Even pairs and prism corners in square-free Berge graphs (2018) (3)
- Avoidable vertices and edges in graphs: Existence, characterization, and applications (2022) (3)
- List 3-Coloring Graphs with No Induced $$P_6+rP_3$$ P 6 + r (2020) (3)
- Three steps towards Gyárfás ’ conjecture (2014) (3)
- Ups and downs of the 4-edge path (2013) (2)
- Excluding a Substar and an Antisubstar (2015) (2)
- Pure pairs. II. Sparse graphs without linear anticomplete pairs (2020) (2)
- Corrigendum to "Bisimplicial vertices in even-hole-free graphs" (2020) (2)
- Cops and robbers on P5-free graphs (2023) (2)
- Some Structural Properties of Unitary Addition Cayley Graphs (2020) (2)
- Strongly perfect claw‐free graphs—A short proof (2019) (2)
- Rainbow Paths and Large Rainbow Matchings (2020) (2)
- Cliques and stable sets in undirected graphs (2014) (2)
- Induced Subgraphs of Graphs with Large Chromatic Number. III. Long Holes (2016) (2)
- Claw-free graphs with strongly perfect complements. Fractional and integral version, Part II: Nontrivial strip-structures (2011) (2)
- Finding minimum clique capacity (2012) (2)
- On the Erd\"os-Lov\'asz Tihany Conjecture for Claw-Free Graphs (2013) (2)
- Small families under subdivision. (2019) (2)
- The structure of bullfree graphs (2008) (2)
- Erdős-Hajnal for cap-free graphs (2021) (2)
- Corrigendum to "Even pairs and prism corners in square-free Berge graphs" [J. Combin. Theory, Ser. B 131 (2018) 12-39] (2018) (2)
- Graph Colouring: from Structure to Algorithms (Dagstuhl Seminar 19271) (2019) (2)
- Holes with hats and Erdős-Hajnal (2020) (2)
- A note on simplicial cliques (2020) (2)
- Graphs with no induced P 5 or P 5 (2014) (1)
- Stable sets in flag spheres (2021) (1)
- Induced subgraphs of graphs with large chromatic number . XII . Two-legged caterpillars (2017) (1)
- Cycle-touching graphs (2022) (1)
- Finding balanced skew partitions in perfect graphs (2015) (1)
- Induced subgraphs and tree decompositions V. Small components of big vertices (2022) (1)
- Pure pairs. X. Excluding six-vertex tournaments (2021) (1)
- Simplicial cliques in claw-free graphs (2012) (1)
- Claw-free graphs I . Clique cutsets (1)
- Induced subgraphs and tree decompositions VI. Graphs with 2-cutsets (2022) (1)
- A Structure Theorem for Claw-Free Perfect Graphs (1)
- Polynomial bounds for chromatic number VII. Disjoint holes (2022) (1)
- On the Erd\H{o}s-Hajnal conjecture for six-vertex tournaments (2015) (1)
- Forbidden Induced Pairs for Perfectness and $\omega$-Colourability of Graphs (2021) (0)
- Pure pairs. X. Tournaments and the strong Erdos-Hajnal property (2022) (0)
- Extending the GyárfásSumner conjecture (2014) (0)
- 2 Ju l 2 01 8 Four-coloring P 6-free graphs . I . Extending an excellent precoloring (2018) (0)
- C O ] 5 F eb 2 01 3 Substitution and χ-Boundedness (2018) (0)
- Detecting a Long Odd Hole (2020) (0)
- Structural Graph Theory (2013) (0)
- Holes with hats and Erd\H{o}s-Hajnal (2020) (0)
- Ðððòòòò Óö Öööòò×× (2008) (0)
- C O ] 2 8 Ju l 2 01 9 Avoidable Vertices and Edges in Graphs ∗ (2019) (0)
- Approximately Coloring Graphs Without Long Induced Paths (2019) (0)
- Even pairs in Berge graphs with no balanced skew-partitions (2023) (0)
- Women's History Month (2013) (0)
- Problems for the Barbados Graph Theory Workshop (2018) (0)
- Une cascade d’exclusion : les lourdeurs administratives et l’accès à la citoyenneté dans le cas du document national d’identité en Argentine (2022) (0)
- Excluding paths and antipaths (2014) (0)
- C O ] 1 D ec 2 01 3 BIPARTITE MINORS (0)
- C O ] 4 F eb 2 01 3 Excluding pairs of graphs (2018) (0)
- A pr 2 01 9 Detecting a long odd hole (2019) (0)
- Proof of the Kalai-Meshulam conjecture (2020) (0)
- New examples of minimal non-strongly-perfect graphs (2020) (0)
- Characterizing and generalizing cycle completable graphs (2023) (0)
- Ju n 20 16 Approximately coloring graphs without long induced paths (2016) (0)
- Even Pairs and Prism Corners in Berge Graphs (2016) (0)
- TWO REMARKS ON THE CACCETTA-HÄGGKVIST CONJECTURE (2021) (0)
- 1 Hadwiger ’ s conjecture and seagulls (2016) (0)
- Pure Pairs. II. Excluding All Subdivisions of A Graph (2021) (0)
- Clique numbers of graph unions (2013) (0)
- Packing seagulls (2012) (0)
- The Sandwich Problem for Decompositions and Almost Monotone Properties (2018) (0)
- The Sandwich Problem for Decompositions and Almost Monotone Properties (2018) (0)
- 1 0 O ct 2 01 9 Small families under subdivision (2019) (0)
- Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices (2017) (0)
- F eb 2 01 8 Four-coloring P 6-free graphs . II . Finding an excellent precoloring (0)
- Toward induced subgraph obstructions to bounded treewidth (2021) (0)
- Tournaments and the Strong Erd\H{o}s-Hajnal Property. (2020) (0)
- Problems for the Barbados Graph Theory Workshop 2017 (2017) (0)
- A counterexample to a conjecture of Schwartz (2012) (0)
- Finding minimum clique capacity (2012) (0)
- OBSTRUCTIONS FOR THREE-COLORING AND LIST THREE-COLORING \bfitH -FREE GRAPHS\ast (2020) (0)
- Forbidden induced pairs for perfectness and ω -colourability of graphs (2021) (0)
- Large Cliques and Stable Sets in Undirected Graphs (2014) (0)
- A short proof of the wonderful lemma (2018) (0)
- Perfect matchings in planar cubic graphs (2012) (0)
- Bipartite graphs with no $K_6$ minor (2022) (0)
- FINDING LARGE H-COLORABLE SUBGRAPHS (2020) (0)
- Excluding a near-clique and a near-anticlique (2012) (0)
- Tournaments and colouring Citation (2012) (0)
- Lines in hypergraphs (2013) (0)
- C O ] 6 M ay 2 02 0 Holes with hats and (2020) (0)
- Attempting perfect hypergraphs (2021) (0)
- Concatenating Bipartite Graphs (2019) (0)

This paper list is powered by the following services:

## Other Resources About Maria Chudnovsky

## What Schools Are Affiliated With Maria Chudnovsky?

Maria Chudnovsky is affiliated with the following schools: