1 citations · 2 across the 7 of their papers we have counts for
10 papers
The -binding function of -directional segment graphs
Lech Duraj, Ross J. Kang, Hoang La +4
Given a positive integer , the class -DIR is defined as all those intersection graphs formed from a finite collection of line segments in having at most s…
A note on the flip distance between non-crossing spanning trees
Nicolas Bousquet, Valentin Gledel, Jonathan Narboni +1
We consider spanning trees of points in convex position whose edges are pairwise non-crossing. Applying a flip to such a tree consists in adding an edge and removing another so…
Vizing's edge-recoloring conjecture holds
Jonathan Narboni
In 1964 Vizing proved that starting from any k-edge-coloring of a graph G one can reach, using only Kempe swaps, a ( + 1)-edge-coloring of G where is the maximum degree of G…
Lower bound for constant-size local certification
Virgina Ardévol Martínez, Marco Caoduro, Laurent Feuilloley +3
Given a network property or a data structure, a local certification is a labeling that allows to efficiently check that the property is satisfied, or that the structure is correct.…
Circular -coloring of some classes of signed graphs
František Kardoš, Jonathan Narboni, Reza Naserasr +1
A circular -coloring of a signed graph is an assignment of points of a circle of circumference to the vertices of such that for each positive edg…
On Vizing's edge colouring question
Marthe Bonamy, Oscar Defrain, Tereza Klimošová +2
Soon after his 1964 seminal paper on edge colouring, Vizing asked the following question: can an optimal edge colouring be reached from any given proper edge colouring through a se…
On a recolouring version of Hadwiger's conjecture
Marthe Bonamy, Marc Heinrich, Clément Legrand-Duchesne +1
We prove that for any , for any large enough , there is a graph that admits no -minor but admits a -colouring that is "frozen" wi…
A note on connected greedy edge colouring
Marthe Bonamy, Carla Groenland, Carole Muller +3
Following a given ordering of the edges of a graph , the greedy edge colouring procedure assigns to each edge the smallest available colour. The minimum number of colours thus i…
A note on deterministic zombies
Valentin Bartier, Laurine Bénéteau, Marthe Bonamy +2
"Zombies and Survivor" is a variant of the well-studied game of "Cops and Robber" where the zombies (cops) can only move closer to the survivor (robber). We consider the determinis…
On the 4-color theorem for signed graphs
František Kardoš, Jonathan Narboni
There are several ways to generalize graph coloring to signed graphs. Máčajová, Raspaud and Škoviera introduced one of them and conjectured that in this setting, for signed planar…