Laboratoire des Sciences pour la Conception, l'Optimisation et la Production

output

20072025

most citedAcyclic edge-coloring using entropy compression

92 citations

Showing 2017 · math.COShow all

2 papers · 2 filters

math.CO2017

On some Graphs with a Unique Perfect Matching

S. Chaplick, M. Fürst, F. Maffray +1

We show that deciding whether a given graph $G$ of size $m$ has a unique perfect matching as well as finding that matching, if it exists, can be done in time $O (m)$ if $G$ is eithe…

math.CO2017

Equitable Colorings of $K_4$ -minor-free Graphs

Rémi De Joannis de Verclos, Jean-Sébastien Sereni

We demonstrate that for every positive integer $Δ$ , every K\_4-minor-free graph with maximum degree $Δ$ admits an equitable coloring with k colors wherek $\geq$ ( $Δ$ +3)/2. This boun…

On some Graphs with a Unique Perfect Matching

Equitable Colorings of K_4-minor-free Graphs

Equitable Colorings of $K_4$ -minor-free Graphs