33 citations · 242 across the 67 of their papers we have counts for
5 papers · 1 filter
Brooks' theorem on powers of graphs
Marthe Bonamy, Nicolas Bousquet
We prove that for , the bound given by Brooks' theorem on the chromatic number of -th powers of graphs of maximum degree can be lowered by 1, even in the case…
Excluding cycles with a fixed number of chords
Pierre Aboulker 'and' Nicolas Bousquet
Trotignon and Vuskovic completely characterized graphs that do not contain cycles with exactly one chord. In particular, they show that such a graph G has chromatic number at most…
The Erdős-Hajnal Conjecture for Paths and Antipaths
Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé
We prove that for every k, there exists such that every graph G on n vertices not inducing a path and its complement contains a clique or a stable set of size $n^{c_k…
Recoloring bounded treewidth graphs
Marthe Bonamy, Nicolas Bousquet
Let be an integer. Two vertex -colorings of a graph are \emph{adjacent} if they differ on exactly one vertex. A graph is \emph{-mixing} if any proper -coloring can be…
Clique versus Independent Set
Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé
Yannakakis' Clique versus Independent Set problem (CL-IS) in communication complexity asks for the minimum number of cuts separating cliques from stable sets in a graph, called CS-…