Twin-width VIIIa: Delineation

2026/07/31 by Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim +3 · 1 voice
Biochemistry, Genetics and Molecular Biology · Medicine · #Assisted Reproductive Technology and Twin Pregnancy #Congenital Heart Disease Studies #Congenital heart defects research

paper · doi:10.1016/j.ejc.2026.104430

openalex publication_date 2026/07/31 · crossref created 2026/07/31 · openalex created_date 2026/08/01 · openalex updated_date 2026/08/02 · crossref deposited 2026/08/02 · crossref indexed 2026/08/02 · crossref issued 2026/12/01 · crossref published 2026/12/01 · crossref published-print 2026/12/01

Citations

• First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs
• Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
• On first-order transductions of classes of graphs
• Twin-width VIII: delineation and win-wins
• Deciding twin-width at most 4 is NP-complete
• Twin-width II: small classes
• Twin-width I: tractable FO model checking
• First-order interpretations of bounded expansion classes
• A New Perspective on FO Model Checking of Dense Graph Classes
• FO Model Checking on Posets of Bounded Width
• Faster Existential FO Model Checking on Posets
• Finding small patterns in permutations in linear time
• FO Model Checking of Interval Graphs
• Testing first-order properties for subclasses of sparse graphs
• Fixed-parameter tractability, definability, and model checking
• The monadic second-order logic of graphs. I. Recognizable sets of finite graphs
• A Combinatorial Problem in Geometry
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Complexity of Finding Embeddings in a k -Tree
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• First order logic and twin-width in tournaments and dense oriented graphs

Discussions

• #New_published_paper Édouard Bonnet, Dibyayan Chakraborty, *Eun Jung Kim*, Noleen Köhler, Raul Lopes, and Stéphan Thomassé, Twin-width VIIIa: Delineation, European J. Comb., 138:104430, December 2026. [bsky, 0 points, 0 comments]