6 papers
Tree-cut decompositions for displaying undominated edge-ends
Max Pitz, Lucas Real
We prove that every graph admits a linked, componental, rooted tree-cut decomposition of finite adhesion that displays all undominated edge-ends. As a first application, we deduce…
On tree-decompositions for infinite chordal graphs
Max Pitz, Lucas Real, Roman Schaut
A graph is chordal if it contains no induced cycle of length four or more. While finite chordal graphs are precisely those admitting tree-decompositions into cliques, this fails fo…
On order-compatible paths in infinite graphs
Max Pitz, Lucas Real, Roman Schaut
Two paths in a graph are order-compatible if their common vertices occur in the same order when travelling from to . Suppose a graph contains an infinite number…
Displaying prescribed sets of ends by linked tree-decompositions
Sandra Albrechtsen, Max Pitz, Roman Schaut
We show that if a subset of the ends of a graph can be displayed by a tree-decomposition of finite adhesion, then it can also be displayed by a linked such tree-decomposit…
Counterexamples regarding linked and lean tree-decompositions of infinite graphs
Sandra Albrechtsen, Raphael W. Jacobs, Paul Knappe +1
Kriz and Thomas showed that every (finite or infinite) graph of tree-width admits a lean tree-decomposition of width . We discuss a number of counterexamples…
All graphs are majority 3-choosable
Jan Ouborny, Max Pitz
Every graph is majority 3-choosable. This generalises the result by Shelah-Milner that every graph has an unfriendly 3-partition, confirming a conjecture of Haslegrave from 2020.