Linear clique-width and modular decomposition

arXiv (Cornell University) 2026 Preprint Open access

Read full text
Authors: Robert Brignall, Michal Opler, Vincent R. Vatter
DOI: 10.48550/arxiv.2602.22089
Cited by: 0

Abstract

A hereditary class of graphs has bounded clique-width if and only if its prime members do, but this lifting property fails for linear clique-width. We prove that a hereditary class has bounded linear clique-width if and only if its prime members do and it contains neither all quasi-threshold graphs nor all complements of quasi-threshold graphs. This generalizes a result of Brignall, Korpelainen, and Vatter, who established the result for cographs.

Fields of Study & Subjects

Advanced Graph Theory Research Complexity and Algorithms in Graphs semigroups and automata theory

Publication details

Journal / source
arXiv (Cornell University)
Publication date
25 February 2026
Language
EN
Document type
Preprint