29 citations · 334 across the 88 of their papers we have counts for
5 papers · 2 filters
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 . We present a purely graph-theoretical algorithm that produces an optimal coloring in poly…
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 there exists such that every undirected graph on vertices that does n…
Induced subgraphs of graphs with large chromatic number. III. Long holes
Maria Chudnovsky, Alex Scott, Paul Seymour
We prove a 1985 conjecture of Gyárfás that for all , every graph with sufficiently large chromatic number contains either a complete subgraph with vertices or an induce…
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 -free graphs, and give the complete list. We remark that, if is connected and not a subgraph of , there are infinitely many 4-cr…
Unavoidable induced subgraphs in large graphs with no homogeneous sets
Maria Chudnovsky, Ringi Kim, Sang-il Oum +1
A homogeneous set of an -vertex graph is a set of vertices () such that every vertex not in is either complete or anticomplete to . A graph is called…