1 citations · 1 across the 2 of their papers we have counts for
4 papers
Graphs of bounded twin-width are quasi-polynomially -bounded
Michał Pilipczuk, Marek Sokołowski
We prove that for every there is a constant such that every graph with twin-width at most and clique number has chromatic number bounded by $2^{γ_t…
Compact representation for matrices of bounded twin-width
Michał Pilipczuk, Marek Sokołowski, Anna Zych-Pawlewicz
For every fixed , we design a data structure that represents a binary matrix that is -twin-ordered. The data structure occupies bits, whi…
Determining 4-edge-connected components in linear time
Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz +1
In this work, we present the first linear time deterministic algorithm computing the 4-edge-connected components of an undirected graph. First, we show an algorithm listing all 3-e…
Bounds on half graph orders in powers of sparse graphs
Marek Sokołowski
Half graphs and their variants, such as ladders, semi-ladders and co-matchings, are combinatorial objects that encode total orders in graphs. Works by Adler and Adler (Eur. J. Comb…