(Even hole, triangle)-free graphs revisited

Beatriz Martins and Nicolas Trotignon ENS de Lyon, CNRS, Université Lyon 1, LIP UMR 5668 69342 Lyon Cedex 07, France · 2026

Read (Even hole, triangle)-free graphs revisited by Beatriz Martins and Nicolas Trotignon ENS de Lyon, CNRS, Université Lyon 1, LIP UMR 5668 69342 Lyon Cedex 07, France (2026) 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-2604-01816.txt.

Description

Martins and Trotignon revisit a paper on (even hole, triangle)-free graphs. The earlier study in fact covers a broader class, the triangle-free odd signable graphs, further generalized here to (theta, triangle, wac)-free graphs. They exhibit a stronger structure theorem describing basic classes and separators. The separators preserve treewidth and several properties. Consequences include a recognition algorithm in time quartic in vertices times edges. Treewidth in the class caps at 4, beating the earlier bound of 5. A criterion settles planarity for graphs in the class.

Catalog record

CREATORBeatriz Martins and Nicolas Trotignon ENS de Lyon, CNRS, Université Lyon 1, LIP UMR 5668 69342 Lyon Cedex 07, France
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE108740
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.01816

Browse the full library · About the Tower of Babel