Maria Chudnovsky

Proof of a conjecture of Plummer and Zha

Maria Chudnovsky, Paul Seymour

Say a graph $G$ is a {\em pentagraph} if every cycle has length at least five, and every induced cycle of odd length has length five. N. Robertson proposed the conjecture that the…

String Graph Obstacles of High Girth and of Bounded Degree

Maria Chudnovsky, David Eppstein, David Fischer

A string graph is the intersection graph of curves in the plane. KratochvÃl previously showed the existence of infinitely many obstacles: graphs that are not string graphs but for…

math.CO2021

A note on simplicial cliques

Maria Chudnovsky, Alex Scott, Paul Seymour +1

Motivated by an application in condensed matter physics and quantum information theory, we prove that every non-null even-hole-free claw-free graph has a simplicial clique, that is…

Coloring Square-free Berge Graphs

Maria Chudnovsky, Irene Lo, Frederic Maffray +2

We consider the class of Berge graphs that do not contain a chordless cycle of length $4$ . We present a purely graph-theoretical algorithm that produces an optimal coloring in poly…

#erdos-posa property#long cycles#distance constraints#graph separators

Far-apart ErdÅs--PÃ³sa property of long cycles

Maria Chudnovsky, Vida DujmoviÄ, GwenaÃ«l Joret +4

The authors prove that for any graph, either it contains many cycles of length at least ℓ that are pairwise far apart, or a small vertex set can be removed to eliminate all such lo…

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…

Non-uniform degrees and rainbow versions of the Caccetta-HÃ¤ggkvist conjecture

Ron Aharoni, Eli Berger, Maria Chudnovsky +2

The Caccetta-HÃ¤ggkvist conjecture (denoted below CHC) states that the directed girth (the smallest length of a directed cycle) $d g i r t h (D)$ of a directed graph $D$ on $n$ vertices…

cs.DS2022

Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws

Tara Abrishami, Maria Chudnovsky, Cemil Dibek +1

For graphs $G$ and $H$ , we say that $G$ is $H$ -free if it does not contain $H$ as an induced subgraph. Already in the early 1980s Alekseev observed that if $H$ is connected, then t…

math.CO2017

Odd holes in bull-free graphs

Maria Chudnovsky, Vaidy Sivaraman

The complexity of testing whether a graph contains an induced odd cycle of length at least five is currently unknown. In this paper we show that this can be done in polynomial time…

On the ErdÃ¶s-LovÃ¡sz Tihany Conjecture for Claw-Free Graphs

Maria Chudnovsky, Alexandra Fradkin, Matthieu Plumettaz

In 1968, ErdÃ¶s and LovÃ¡sz conjectured that for every graph $G$ and all integers $s, t \geq 2$ such that $s + t - 1 = I ¨ (G) > I ¨ (G)$ , there exists a partition $(S, T)$ of the vertex set of…

List- $k$ -Coloring $H$ -free graphs for all $k > 4$

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Given an integer $k > 4$ and a graph $H$ , we prove that, assuming P $\neq =$ NP, the List- $k$ -Coloring Problem restricted to $H$ -free graphs can be solved in polynomial time if and only…

Induced subgraphs of graphs with large chromatic number. XI. Orientations

Maria Chudnovsky, Alex Scott, Paul Seymour

Fix an oriented graph H, and let G be a graph with bounded clique number and very large chromatic number. If we somehow orient its edges, must there be an induced subdigraph isomor…

Vertex-minors and the ErdÅs-Hajnal conjecture

Maria Chudnovsky, Sang-il Oum

We prove that for every graph $H$ , there exists $ε > 0$ such that every $n$ -vertex graph with no vertex-minors isomorphic to $H$ has a pair of disjoint sets $A$ , $B$ of ver…

Induced subgraphs and tree decompositions XI. Local structure in even-hole-free graphs of large treewidth

Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1

We prove a conjecture of Sintiari and Trotignon that every even-hole-free graph of sufficiently large treewidth contains a four-vertex induced subgraph with at least five edges (th…

Towards Erdos-Hajnal for graphs with no 5-hole

Maria Chudnovsky, Jacob Fox, Alex Scott +2

The Erdos-Hajnal conjecture says that for every graph $H$ there exists $c > 0$ such that $max (I^\pm (G), I ¨ (G)) \geq n^{c}$ for every $H$ -free graph $G$ with $n$ vertices, and this is still…

Graphs with no even holes and no sector wheels are the union of two chordal graphs

Tara Abrishami, Eli Berger, Maria Chudnovsky +1

Sivaraman conjectured that if $G$ is a graph with no induced even cycle then there exist sets $X_{1}, X_{2} \subseteq V (G)$ satisfying $V (G) = X_{1} \cup X_{2}$ such that the induced graph…

Polynomial bounds for chromatic number VII. Disjoint holes

Maria Chudnovsky, Alex Scott, Paul Seymour +1

A hole in a graph $G$ is an induced cycle of length at least four, and a $k$ -multihole in $G$ is a set of pairwise disjoint and nonadjacent holes. It is well known that if $G$ does…

Tree independence number I. (Even hole, diamond, pyramid)-free graphs

Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +3

The tree-independence number tree- $I^\pm$ , first defined and studied by Dallard, MilaniÄ and Å torgel, is a variant of treewidth tailored to solving the maximum independent set probl…

cs.DM2012

Edge-colouring eight-regular planar graphs

Maria Chudnovsky, Katherine Edwards, Paul Seymour

It was conjectured by the third author in about 1973 that every $d$ -regular planar graph (possibly with parallel edges) can be $d$ -edge-coloured, provided that for every odd set $X…

Pure pairs. I. Trees and linear anticomplete pairs

Maria Chudnovsky, Alex Scott, Paul Seymour +1

The Erdos-Hajnal Conjecture asserts that for every graph H there is a constant c > 0 such that every graph G that does not contain H as an induced subgraph has a clique or stable s…

Pure pairs. II. Excluding all subdivisions of a graph

Maria Chudnovsky, Alex Scott, Paul Seymour +1

We prove for every graph H there exists a>0 such that, for every graph G with at least two vertices, if no induced subgraph of G is a subdivision of H, then either some vertex of G…

cs.DM2014

4-coloring $P_{6}$ -free graphs with no induced 5-cycles

Maria Chudnovsky, Peter Maceli, Juraj Stacho +1

We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle $C_{5}$ and no induced 6-vertex path $P_{6}$ .

Sparse graphs with no polynomial-sized anticomplete pairs

Maria Chudnovsky, Jacob Fox, Alex Scott +2

A graph is " $H$ -free" if it has no induced subgraph isomorphic to $H$ . A conjecture of Conlon, Fox and Sudakov states that for every graph $H$ , there exists $s > 0$ such that in ever…

Disjoint paths in unions of tournaments

Maria Chudnovsky, Alex Scott, Paul Seymour

Given $k$ pairs of vertices $(s_{i}, t_{i}) (1 \leq i \leq k)$ of a digraph $G$ , how can we test whether there exist vertex-disjoint directed paths from $s_{i}$ to $t_{i}$ for $1 \leq i \leq k$ ? T…

cs.DM2013

Detecting an induced net subdivision

Maria Chudnovsky, Paul Seymour, Nicolas Trotignon

A {\em net} is a graph consisting of a triangle $C$ and three more vertices, each of degree one and with its neighbour in $C$ , and all adjacent to different vertices of $C$ . We giv…

Induced Minors and Coarse Tree Decompositions

Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +1

Let $G$ be a graph, $S \subseteq V (G)$ be a vertex set in $G$ and $r$ be a positive integer. The distance $r$ -independence number of $S$ is the size of the largest subset $I \subse…

Dominated balanced separators in wheel-induced-minor-free graphs

Maria Chudnovsky, J. Pascal Gollin, MatjaÅ¾ Krnc +1

Gartland and Lokshtanov conjectured that every graph that excludes some planar graph as an induced minor has a balanced separator, that is, a separator whose deletion leaves every…

Coarse Balanced Separators and Tree-Decompositions

Maria Chudnovsky, Robert Hickingbotham

A classical result of Robertson and Seymour (1986) states that the treewidth of a graph is linearly tied to its separation number: the smallest integer $k$ such that, for every wei…

Induced subgraphs and tree decompositions IX. Grid theorem for perforated graphs

Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1

The celebrated ErdÅs-PÃ³sa Theorem, in one formulation, asserts that for every $c \geq 1$ , graphs with no subgraph (or equivalently, minor) isomorphic to the disjoint union of $c$ …

Proof of the Kalai-Meshulam conjecture

Maria Chudnovsky, Alex Scott, Paul Seymour +1

Let $G$ be a graph, and let $f_{G}$ be the sum of $(- 1)^{∣ A ∣}$ , over all stable sets $A$ . If $G$ is a cycle with length divisible by three, then $f_{G} = \pm 2$ . Motivated by topologica…

Localized ErdÅs-PÃ³sa Property for Subdivisions

Icey Siyi Ai, Maria Chudnovsky, Julien Codsi

For a graph $H$ , we say that $H$ has the ErdÅs-PÃ³sa property for subdivisions with function $f$ , if for every graph $G$ , either $G$ contains (as a subgraph) $k + 1$ pairwise disjoi…

Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs

Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1

Given an integer $c \in N$ , we say a graph $G$ is $c$ -pinched if $G$ does not contain an induced subgraph consisting of $c$ cycles, all going through a single common vertex…

Induced subgraphs and tree decompositions XVIII. Obstructions to bounded pathwidth

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

The pathwidth of a graph $G$ is the smallest $w \in N$ such that $G$ can be constructed from a sequence of graphs, each on at most $w + 1$ vertices, by gluing them together i…

Induced subgraphs and tree decompositions XIII. Basic obstructions in $H$ -free graphs for finite $H$

Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1

Unlike minors, the induced subgraph obstructions to bounded treewidth come in a large variety, including, for every $t \geq 1$ , the $t$ -basic obstructions: the graphs $K_{t + 1}$ and…

Strengthening Rodl's theorem

Maria Chudnovsky, Alex Scott, Paul Seymour +1

What can be said about the structure of graphs that do not contain an induced copy of some graph H? Rodl showed in the 1980s that every H-free graph has large parts that are very d…

List-three-coloring $P_{t}$ -free graphs with no induced 1-subdivision of $K_{1, s}$

Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong

Let $s$ and $t$ be positive integers. We use $P_{t}$ to denote the path with $t$ vertices and $K_{1, s}$ to denote the complete bipartite graph with parts of size $1$ and $s$ respecti…

Immersion in four-edge-connected graphs

Maria Chudnovsky, ZdenÄk DvoÅÃ¡k, Tereza KlimoÅ¡ovÃ¡ +1

Fix g>1. Every graph of large enough tree-width contains a g x g grid as a minor; but here we prove that every four-edge-connected graph of large enough tree-width contains a g x g…

Detecting a long odd hole

Maria Chudnovsky, Alex Scott, Paul Seymour

For each integer $t \geq 5$ , we give a polynomial-time algorithm to test whether a graph contains an induced cycle with length at least $t$ and odd.

Induced Cycles of Many Lengths

Maria Chudnovsky, Ilya Maier

Let $G$ be a graph and let $cl (G)$ be the number of distinct induced cycle lengths in $G$ . We show that for $c, t \in N$ , every graph $G$ that does not contain an in…

Large rainbow matchings in general graphs

Ron Aharoni, Eli Berger, Maria Chudnovsky +2

By a theorem of Drisko, any $2 n - 1$ matchings of size $n$ in a bipartite graph have a partial rainbow matching of size $n$ . Inspired by discussion of BarÃ¡t, GyÃ¡rfÃ¡s and SÃ¡rkÃ¶zy…

Induced subgraphs and tree decompositions XVII. Anticomplete sets of large treewidth

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Two sets $X, Y$ of vertices in a graph $G$ are "anticomplete" if $X \cap Y = \emptyset$ and there is no edge in $G$ with an end in $X$ and an end in $Y$ . We prove that every graph $…

math.CO2015

On the ErdÅs-Hajnal conjecture for six-vertex tournaments

Eli Berger, Krzysztof Choromanski, Maria Chudnovsky

A celebrated unresolved conjecture of ErdÅs and Hajnal states that for every undirected graph $H$ there exists $I^µ (H) > 0$ such that every undirected graph on $n$ vertices that does…

Excluding Pairs of Graphs

Maria Chudnovsky, Alex Scott, Paul Seymour

For a graph $G$ and a set of graphs $H$ , we say that $G$ is {\em $H$ -free} if no induced subgraph of $G$ is isomorphic to a member of $H$ . Given an in…

Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs

Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi +1

A hole in a graph $G$ is an induced cycle of length at least four, and an even hole is a hole of even length. The diamond is the graph obtained from the complete graph $K_{4}$ by rem…

Stable sets in flag spheres

Maria Chudnovsky, Eran Nevo

We provide lower and upper bounds on the minimum size of a maximum stable set over graphs of flag spheres, as a function of the dimension of the sphere and the number of vertices.…

Obstructions for three-coloring graphs without induced paths on six vertices

Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt +1

We prove that there are 24 4-critical $P_{6}$ -free graphs, and give the complete list. We remark that, if $H$ is connected and not a subgraph of $P_{6}$ , there are infinitely many 4-cr…

List-three-coloring graphs with no induced $P_{6} + r P_{3}$

Maria Chudnovsky, Shenwei Huang, Sophie Spirkl +1

For an integer $r$ , the graph $P_{6} + r P_{3}$ has $r + 1$ components, one of which is a path on $6$ vertices, and each of the others is a path on $3$ vertices. In this paper we provide a…

Cops and robbers on $P_{5}$ -free graphs

Maria Chudnovsky, Sergey Norin, Paul Seymour +1

We prove that every connected $P_{5}$ -free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected $P_{5}$ -free grap…

Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth

Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi +1

A theta is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $H$ of graphs, we s…

Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs

Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +2

A generalized $t$ -pyramid is a graph obtained from a certain kind of tree (a subdivided star or a subdivided cubic caterpillar) and the line graph of a subdivided cubic caterpillar…

cs.DS2023

Sparse induced subgraphs in P_6-free graphs

Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk +4

We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in CMSO2 logic, most notably Feedback Vertex Se…

Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

A clock is a graph consisting of an induced cycle $C$ and a vertex not in $C$ with at least two non-adjacent neighbours in $C$ . We show that every clock-free graph of large treewid…

Induced subgraphs and tree-decompositions VII. Basic obstructions in $H$ -free graphs

Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +2

We say a class $C$ of graphs is clean if for every positive integer $t$ there exists a positive integer $w (t)$ such that every graph in $C$ with treewidth more…

Tree independence number V. Walls and claws

Maria Chudnovsky, Julien Codsi, Daniel Lokshtanov +2

Given a family $H$ of graphs, we say that a graph $G$ is $H$ -free if no induced subgraph of $G$ is isomorphic to a member of $H$ . Let $S_{t, t, t}$ be t…

Minors of plane digraphs

Maria Chudnovsky, Paul Seymour

A digraph $H$ is a ``semi-strong minor'' of another, $G$ , if a subdivision of $H$ can be obtained from a subdigraph of $G$ by contracting strongly-connected subdigraphs to single v…

Strictly Metrizable Graphs are Minor-Closed

Maria Chudnovsky, Daniel Cizma, Nati Linial

A consistent path system in a graph $G$ is an collection of paths, with exactly one path between any two vertices in $G$ . A path system is said to be consistent if it is intersecti…

#induced subgraphs#path exclusion#biclique exclusion#ramsey-type bounds

Excluding paths and bicliques

Maria Chudnovsky, Julien Codsi, MatjaÅ¾ Krnc +1

The paper improves the known Ramsey‑type bound on the maximum length of a path in graphs that exclude a fixed path and a biclique as induced subgraphs, showing it can be taken sing…

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…

math.CO2014

Disjoint dijoins

Maria Chudnovsky, Katherine Edwards, Ringi Kim +2

A dijoin in a digraph is a set of edges meeting every directed cut. D. R. Woodall conjectured in 1976 that if G is a digraph, and every directed cut of G has at least k edges, then…

math.CO2016

Fair representation by independent sets

Ron Aharoni, Noga Alon, Eli Berger +4

For a hypergraph $H$ let $I^^{2} (H)$ denote the minimal number of edges from $H$ covering $V (H)$ . An edge $S$ of $H$ is said to represent {\em fairly} (resp. {\em almost fairly}) a par…

cs.DS2024

Max Weight Independent Set in sparse graphs with no long claws

Tara Abrishami, Maria Chudnovsky, Cemil Dibek +2

We revisit the recent polynomial-time algorithm for the MAX WEIGHT INDEPENDENT SET (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component i…

Strongly Perfect Claw-free Graphs -- A Short Proof

Maria Chudnovsky, Cemil Dibek

A graph is strongly perfect if every induced subgraph H has a stable set that meets every maximal clique of H. A graph is claw-free if no vertex has three pairwise non-adjacent nei…

Forbidden induced pairs for perfectness and $I ¨ $ -colourability of graphs

Maria Chudnovsky, Adam Kabela, Binlong Li +1

We characterise the pairs of graphs ${X, Y}$ such that all ${X, Y}$ -free graphs (distinct from $C_{5}$ ) are perfect. Similarly, we characterise pairs ${X, Y}$ such that a…

Tree-independence number VII. Excluding a star

Maria Chudnovsky, Jadwiga CzyÅ¼ewska, Marcin Pilipczuk +1

We prove that for every fixed integer $s$ and every planar graph $H$ , the class of $H$ -induced-minor-free and $K_{1, s}$ -induced-subgraph-free graphs has polylogarithmic tree-indepe…

Reuniting $I ¨ $ -boundedness with polynomial $I ¨ $ -boundedness

Maria Chudnovsky, Linda Cook, James Davies +1

A class $F$ of graphs is $I ¨ $ -bounded if there is a function $f$ such that $I ¨ (H) \leq f (I ¨ (H))$ for all induced subgraphs $H$ of a graph in $F$ . If $f$ can be ch…

Tree Independence Number IV. Even-hole-free Graphs

Maria Chudnovsky, Peter Gartland, Sepehr Hajebi +2

We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constan…

Obstructions for three-coloring and list three-coloring $H$ -free graphs

Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt +1

A graph is $H$ -free if it has no induced subgraph isomorphic to $H$ . We characterize all graphs $H$ for which there are only finitely many minimal non-three-colorable $H$ -free grap…

math.CO2014

Three-coloring graphs with no induced seven-vertex path I : the triangle-free case

Maria Chudnovsky, Peter Maceli, Mingxian Zhong

In this paper, we give a polynomial time algorithm which determines if a given triangle-free graph with no induced seven-vertex path is 3-colorable, and gives an explicit coloring…

Tree independence number II. Three-path-configurations

Maria Chudnovsky, Sepehr Hajebi, Daniel Lokshtanov +1

A three-path-configuration is a graph consisting of three pairwise internally-disjoint paths the union of every two of which is an induced cycle of length at least four. A graph is…

Finding a shortest odd hole

Maria Chudnovsky, Alex Scott, Paul Seymour

An odd hole in a graph is a induced cycle with odd length greater than 3. In an earlier paper (with Sophie Spirkl), solving a longstanding open problem, we gave a polynomial-time a…

cs.DS2023

Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs

Maria Chudnovsky, Marcin Pilipczuk, MichaÅ Pilipczuk +1

In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this c…

Even-hole-free graphs still have bisimplicial vertices

Maria Chudnovsky, Paul Seymour

A {\em hole} in a graph is an induced subgraph which is a cycle of length at least four. A hole is called {\em even} if it has an even number of vertices. An {\em even-hole-free} g…

Concatenating bipartite graphs

Maria Chudnovsky, Patrick Hompe, Alex Scott +2

Let $x, y \in (0, 1]$ and let $A, B, C$ be disjoint nonempty subsets of a graph $G$ , where every vertex in $A$ has at least $x ∣ B ∣$ neighbours in $B$ , and every vertex in $B$ has at least…

Characterizing and generalizing cycle completable graphs

Maria Chudnovsky, Ian Malcolm Johnson McInnis

The family of cycle completable graphs has several cryptomorphic descriptions, the equivalence of which has heretofore been proven by a laborious implication-cycle that detours thr…

math.CO2021

Graphs with polynomially many minimal separators

Tara Abrishami, Maria Chudnovsky, Cemil Dibek +3

We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the…

cs.DS2023

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…

Tree-independence number and forbidden induced subgraphs: excluding a $6$ -vertex path and a $(2, t)$ -biclique

Maria Chudnovsky, Julien Codsi, J. Pascal Gollin +2

We show that for every positive integer $t \geq 2$ there exists an integer $s$ such that every graph that contains no induced subgraph isomorphic to either the $6$ -vertex path or…

Tree-independence number VI. Thetas and pyramids

Maria Chudnovsky, Julien Codsi

Given a family $H$ of graphs, we say that a graph $G$ is $H$ -free if no induced subgraph of $G$ is isomorphic to a member of $H$ . Let $W_{t \times t}$ …

math.CO2019

Detecting an odd hole

Maria Chudnovsky, Alex Scott, Paul Seymour +1

A hole in a graph G is an induced cycle of length at least four; an antihole is a hole in the complement of G. In 2005, Chudnovsky, Cornuejols, Liu, Seymour and Vuskovic showed tha…

Pure pairs. X. Tournaments and the strong Erdos-Hajnal property

Maria Chudnovsky, Alex Scott, Paul Seymour +1

A pure pair in a tournament $G$ is an ordered pair $(A, B)$ of disjoint subsets of $V (G)$ such that every vertex in $B$ is adjacent from every vertex in $A$ . Which tournaments $H$ h…

math.CO2017

Colouring perfect graphs with bounded clique number

A graph is perfect if the chromatic number of every induced subgraph equals the size of its largest clique, and an algorithm of GrÃ¶tschel, LovÃ¡sz, and Schrijver from 1988 finds a…

math.CO2021

Erdos-Hajnal for graphs with no 5-hole

Maria Chudnovsky, Alex Scott, Paul Seymour +1

The Erdos-Hajnal conjecture says that for every graph H there exists c>0 such that every graph G not containing H as an induced subgraph has a clique or stable set of cardinality a…

math.CO2016

Approximately coloring graphs without long induced paths

Maria Chudnovsky, Oliver Schaudt, Sophie Spirkl +2

It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on $t$ vertices, for fixed $t$ . We…

math.CO2015

Excluding four-edge paths and their complements

Maria Chudnovsky, Peter Maceli, Irena Penev

We prove that a graph G contains no induced four-edge path and no induced complement of a four-edge path if and only if G is obtained from five-cycles and split graphs by repeatedl…

cs.DM2012

Edge-colouring seven-regular planar graphs

Maria Chudnovsky, Katherine Edwards, Ken-ichi Kawarabayashi +1

A conjecture due to the fourth author states that every $d$ -regular planar multigraph can be $d$ -edge-coloured, provided that for every odd set $X$ of vertices, there are at least…

Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree

Tara Abrishami, Maria Chudnovsky, Kristina VuÅ¡koviÄ

Treewidth is a parameter that emerged from the study of minor closed classes of graphs (i.e. classes closed under vertex and edge deletion, and edge contraction). It in some sense…

Colouring t-perfect graphs

Maria Chudnovsky, Linda Cook, James Davies +2

Perfect graphs can be described as the graphs whose stable set polytopes are defined by their non-negativity and clique inequalities (including edge inequalities). In 1975, ChvÃ¡ta…

Holes with hats and ErdÅs-Hajnal

Maria Chudnovsky, Paul Seymour

A "hole-with-hat" in a graph $G$ is an induced subgraph of $G$ that consists of a cycle of length at least four, together with one further vertex that has exactly two neighbours in…

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-…

Induced minors and subpolynomial treewidth

Maria Chudnovsky, Julien Codsi, David Fischer +1

Given a family $H$ of graphs, we say that a graph $G$ is $H$ -induced-minor-free if no induced minor of $G$ is isomorphic to a member of $H$ , We denote…

cs.DM2020

On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five

Maria Chudnovsky, Marcin Pilipczuk, MichaÅ Pilipczuk +1

A hole in a graph is an induced cycle of length at least $4$ , and an antihole is the complement of an induced cycle of length at least $4$ . A hole or antihole is long if its length…

math.CO2015

Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyarfas' conjectures

Maria Chudnovsky, Paul Seymour, Alex Scott

Gyarfas conjectured in 1985 that for all $k$ , $l$ , every graph with no clique of size more than $k$ and no odd hole of length more than $l$ has chromatic number bounded by a functi…

cs.DM2011

A local strengthening of Reed's Ï, Î, Ï conjecture for quasi-line graphs

Maria Chudnovsky, Andrew D. King, Matthieu Plumettaz +1

Reed's $I ¨ $ , $I^$ , $I ¨ $ conjecture proposes that every graph satisfies $I ¨ \leq ⌈ \frac{1}{2} (I^ + 1 + I ¨ )⌉$ ; it is known to hold for all claw-free graphs. In this paper we consid…

(Treewidth, Clique)-Boundedness and Poly-logarithmic Tree-Independence

Maria Chudnovsky, Ajaykrishnan E S, Daniel Lokshtanov

An independent set in a graph $G$ is a set of pairwise non-adjacent vertices. A tree decomposition of $G$ is a pair $(T, I ¨ )$ where $T$ is a tree and $Ï: V(T) \rightarrow 2^{V(G)}…

Cooperative colorings of trees and of bipartite graphs

Ron Aharoni, Eli Berger, Maria Chudnovsky +2

Given a system $(G_{1}, \dots, G_{m})$ of graphs on the same vertex set $V$ , a cooperative coloring is a choice of vertex sets $I_{1}, \dots, I_{m}$ , such that $I_{j}$ is independent in $G…

Induced subgraphs and tree decompositions VI. Graphs with 2-cutsets

Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi +1

This paper continues a series of papers investigating the following question: which hereditary graph classes have bounded treewidth? We call a graph $t$ -clean if it does not contai…

cs.DM2012

Optimal antithickenings of claw-free trigraphs

Maria Chudnovsky, Andrew D. King

Chudnovsky and Seymour's structure theorem for claw-free graphs has led to a multitude of recent results that exploit two structural operations: {\em compositions of strips} and {\…

math.CO2002

The strong perfect graph theorem

Maria Chudnovsky, Neil Robertson, Paul Seymour +1

A graph G is perfect if for every induced subgraph H, the chromatic number of H equals the size of the largest complete subgraph of H, and G is Berge if no induced subgraph of G is…