M. Chudnovsky

activity

20022024

χ

-Boundedness

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

collaborators

Showing 2018 · math.COShow all

9 papers · 2 filters

math.CO2018

Coloring graphs with no induced five-vertex path or gem

M. Chudnovsky, T. Karthick, P. Maceli +1

For a graph $G$ , let $χ (G)$ and $ω (G)$ respectively denote the chromatic number and clique number of $G$ . We give an explicit structural description of ( $P_{5}$ ,gem)-free graphs, and…

math.CO2018★ 1 cited

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…

math.CO2018

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…

math.CO2018

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…

math.CO2018

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…

math.CO2018★ 4 cited

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…

Coloring graphs with no induced five-vertex path or gem

Sparse graphs with no polynomial-sized anticomplete pairs

Proof of the Kalai-Meshulam conjecture

Pure pairs. I. Trees and linear anticomplete pairs

List-three-coloring graphs with no induced P6​+rP3​

Cooperative colorings of trees and of bipartite graphs

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