4 papers
Twin-width and polynomial kernels
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald +2
We study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main re…
Twin-width IV: ordered graphs and matrices
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez +3
We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a…
Degeneracy of -free and -free graphs with no large complete bipartite subgraphs
Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk +3
A hereditary class of graphs is \emph{-bounded} if there exists a function such that every graph satisfies , where $χ(G)…
Edge-partitioning 3-edge-connected graphs into paths
Tereza Klimošová, Stéphan Thomassé
We show that for every l, there exists d_l such that every 3-edge-connected graph with minimum degree d_l can be edge-partitioned into paths of length l (provided that its number o…