Trees in Graphs of Large Linear Cliquewidth

Mikołaj Bojańczyk, Pierre Ohlmann · 2025

Read Trees in Graphs of Large Linear Cliquewidth by Mikołaj Bojańczyk, Pierre Ohlmann (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-17556.txt.

Introduction

Mikołaj Bojańczyk and Pierre Ohlmann prove a graph theory result in a 2025 paper. Graphs are webs of points and links, and some webs resist being built from a small set of simple moves. A classic result says that webs that are hard to split into narrow paths must contain every tree shape hidden inside them.

The pair prove a dense-web cousin of that result. They give a fixed family of tree-like patterns and show that any web family with one width measure capped can still hide huge patterns. Those patterns can stand in for all trees under one kind of translation, and for split binary trees under a stricter one. The result fills a gap in showing that one ranking of graph families has no holes. It ties width, patterns, and logic into one clean claim.

Catalog record

CREATORMikołaj Bojańczyk, Pierre Ohlmann
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE233 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-17556

Browse the full library · About the Tower of Babel