On the clique-width of (4K(1), C-4, C-5, C-7)-free graphs

Abstract

We prove that (4K(1), C-4, C-5, C-7)-free graphs that are not chordal have unbounded clique-width. This disproves a conjecture from Fraser et al. (2017). (C) 2020 Elsevier B.V.

All rights reserved.

Keywords

• Clique-width
• Forbidden induced subgraphs