43 citations · 235 across the 46 of their papers we have counts for
4 papers · 2 filters
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 vertices, for fixed . We…
A Variant of the Erdős-Sós Conjecture
Frédéric Havet, Bruce Reed, Maya Stein +1
A well-known conjecture of Erdős and Sós states that every graph with average degree exceeding contains every tree with edges as a subgraph. We propose a variant of this…
Regularity inheritance in pseudorandom graphs
Peter Allen, Julia Böttcher, Jozef Skokan +1
Advancing the sparse regularity method, we prove one-sided and two-sided regularity inheritance lemmas for subgraphs of bijumbled graphs, improving on results of Conlon, Fox and Zh…
Clique coloring -EPG graphs
Flavia Bonomo, María Pía Mazzoleni, Maya Stein
We consider the problem of clique coloring, that is, coloring the vertices of a given graph such that no (maximal) clique of size at least two is monocolored. It is known that inte…