22 citations · 112 across the 37 of their papers we have counts for
6 papers · 2 filters
Fast Recoloring of Sparse Graphs
Nicolas Bousquet, Guillem Perarnau
In this paper, we show that for every graph of maximum average degree bounded away from , any -coloring can be transformed into any other one within a polynomial number o…
Acyclic edge colourings of graphs with large girth
Xing Shi Cai, Guillem Perarnau, Bruce Reed +1
An edge colouring of a graph is called acyclic if it is proper and every cycle contains at least three colours. We show that for every , there exists a $g=g(\var…
Decomposition of bounded degree graphs into -free subgraphs
Ross J. Kang, Guillem Perarnau
We prove that every graph with maximum degree admits a partition of its edges into parts (as ) none of which contains as a subgraph. This bound is…
Correlation among runners and some results on the Lonely Runner Conjecture
Guillem Perarnau, Oriol Serra
The Lonely Runner Conjecture was posed independently by Wills and Cusick and has many applications in different mathematical fields, such as diophantine approximation. This well-kn…
Existence of spanning -free subgraphs with large minimum degree
Guillem Perarnau, Bruce Reed
Let be a family of fixed graphs and let be large enough. For every -regular graph , we study the existence of a spanning -free subgraph of …
Large subgraphs without short cycles
Florent Foucaud, Michael Krivelevich, Guillem Perarnau
We study two extremal problems about subgraphs excluding a family $\F$ of graphs. i) Among all graphs with edges, what is the smallest size $f(m,\F)$ of a largest $\F$--free su…