Uncountably many minimal hereditary classes of graphs of unbounded clique-width

DOI10.37236/10483MaRDI QIDQ2121810zbMATH OpenOpenAlexWikidataFDO

Authors Robert Brignall, Daniel G. Cocks

Publication date 4 April 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license File:Creative commons license with attribution.png Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2104.00412

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

almost periodic wordbipartite hereditary graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics on words (68R15)

Abstract: Given an infinite word over the alphabet $0,1,2,3$, we define a class of bipartite hereditary graphs $mathcal{G}^{a}lpha$, and show that $mathcal{G}^{a}lpha$ has unbounded clique-width unless $alpha$ contains at most finitely many non-zero letters. We also show that $mathcal{G}^{a}lpha$ is minimal of unbounded clique-width if and only if $alpha$ belongs to a precisely defined collection of words $Gamma$. The set $Gamma$ includes all almost periodic words containing at least one non-zero letter, which both enables us to exhibit uncountably many pairwise distinct minimal classes of unbounded clique width, and also proves one direction of a conjecture due to Collins, Foniok, Korpelainen, Lozin and Zamaraev. Finally, we show that the other direction of the conjecture is false, since $Gamma$ also contains words that are emph{not} almost periodic.

Review text

Summary: Given an infinite word over the alphabet \(\{0,1,2,3\}\), we define a class of bipartite hereditary graphs \(\mathcal{G}^\alpha \), and show that \(\mathcal{G}^\alpha\) has unbounded clique-width unless \(\alpha\) contains at most finitely many non-zero letters. We also show that \(\mathcal{G}^\alpha\) is minimal of unbounded clique-width if and only if \(\alpha\) belongs to a precisely defined collection of words \(\Gamma\). The set \(\Gamma\) includes all almost periodic words containing at least one non-zero letter, which both enables us to exhibit uncountably many pairwise distinct minimal classes of unbounded clique width, and also proves one direction of a conjecture due to \textit{A. Collins} et al. [Discrete Appl. Math. 248, 145--152 (2018; Zbl 1395.05051)]. Finally, we show that the other direction of the conjecture is false, since \(\Gamma\) also contains words that are not almost periodic.

Recommendations

• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• Infinitely many minimal classes of graphs of unbounded clique-width
• A new graph construction of unbounded clique-width
• Clique-width and the speed of hereditary properties
• Well-quasi-ordering versus clique-width

Cites work

• A new graph construction of unbounded clique-width
• Approximating clique-width and branch-width
• Clique-width for hereditary graph classes
• Graph minors. V. Excluding a planar graph
• Graph theory
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 590283 (Why is no real title available?)
• scientific article; zbMATH DE number 2191997 (Why is no real title available?)
• Infinitely many minimal classes of graphs of unbounded clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Minimal classes of graphs of unbounded clique-width
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• On the clique-width of some perfect graph classes
• Rank-width and vertex-minors
• Substitutions in dynamics, arithmetics and combinatorics
• The grid theorem for vertex-minors
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Upper bounds to the clique width of graphs

Cited in

(8)

• Infinitely many minimal classes of graphs of unbounded clique-width
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• A new graph construction of unbounded clique-width
• Bounding the mim‐width of hereditary graph classes
• A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width
• \(t\)-sails and sparse hereditary classes of unbounded tree-width
• MSO undecidability for hereditary classes of unbounded clique-width
• An overview of universal obstructions for graph parameters

This page was built for publication: Uncountably many minimal hereditary classes of graphs of unbounded clique-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2121810)