8 citations · 11 across the 16 of their papers we have counts for
9 papers · 1 filter
Variants of Merge-Width and Applications
Karolina Drabik, Maël Dumas, Colin Geniet +3
Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We prove the equivalence of sev…
Basis Number of Graphs Excluding Minors
Colin Geniet, Ugo Giocanti
The basis number of a graph is the minimum such that the cycle space of is generated by a family of cycles using each edge at most times. A classical result of Mac…
Transducing Linear Decompositions of Tournaments
Colin Geniet, Fatemeh Ghasemi, Mamadou Moustapha Kanté
Bojańczyk, Pilipczuk, and Grohe [LICS '18] proved that for graphs of bounded linear clique-width, clique-decompositions of bounded width can be produced by a CMSO transduction. We…
Separability Properties of Monadically Dependent Graph Classes
Édouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis +5
A graph class is monadically dependent if one cannot interpret all graphs in colored graphs from using a fixed first-order interpretation. We prove that m…
-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs
Marthe Bonamy, Colin Geniet
Merge-width, recently introduced by Dreier and Toruńczyk, is a common generalisation of bounded expansion classes and twin-width for which the first-order model checking problem re…
Half-integral Erdős-Pósa property for non-null - paths
Vera Chekan, Colin Geniet, Meike Hatzel +4
For a group , a -labelled graph is an undirected graph where every orientation of an edge is assigned an element of so that opposite orientations of the same edge are…
Factoring Pattern-Free Permutations into Separable ones
Édouard Bonnet, Romain Bourneuf, Colin Geniet +1
We show that for any permutation there exists an integer such that every permutation avoiding as a pattern is a product of at most separable permutations. In ot…
A tamed family of triangle-free graphs with unbounded chromatic number
Édouard Bonnet, Romain Bourneuf, Julien Duron +3
We construct a hereditary class of triangle-free graphs with unbounded chromatic number, in which every non-trivial graph either contains a pair of non-adjacent twins or has an edg…
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Édouard Bonnet, Hugues Déprés +5
A graph is -free if it does not contain pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite g…