Clique-width and the speed of hereditary properties

MaRDI QIDQ1010945zbMATH OpenFDO

Authors J. Martínez

Publication date 7 April 2009

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

Full work available at URL https://eudml.org/doc/117311, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r35.html

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

clique-widthdiscrete layershereditary class of graphsrates of growthspeed of hereditary classes

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) 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)

Review text

Summary: We study the relationship between the number of \(n\)-vertex graphs in a hereditary class \(\mathcal X\), also known as the speed of the class \(\mathcal X\), and boundedness of the clique-width in this class. We show that if the speed of \(\mathcal X\) is faster than \(n!c^n\) for any \(c\), then the clique-width of graphs in \(\mathcal X\) is unbounded, while if the speed does not exceed the Bell number \(B_n\), then the clique-width is bounded by a constant. The situation in the range between these two extremes is more complicated. This area contains both classes of bounded and unbounded clique-width. Moreover, we show that classes of graphs of unbounded clique-width may have slower speed than classes where the clique-width is bounded.

Recommendations

• Clique-width for hereditary graph classes
• scientific article; zbMATH DE number 1979486
• Linear clique-width for hereditary classes of cographs
• Infinitely many minimal classes of graphs of unbounded clique-width
• Clique-width for graph classes closed under complementation

Cited in

(18)

• Uncountably many minimal hereditary classes of graphs of unbounded clique-width
• Faster recognition of clique-Helly and hereditary clique-Helly graphs
• Infinitely many minimal classes of graphs of unbounded clique-width
• Linear clique-width for hereditary classes of cographs
• Locally bounded coverings and factorial properties of graphs
• On factorial properties of chordal bipartite graphs
• scientific article; zbMATH DE number 1979486 (Why is no real title available?)
• Implicit representations and factorial properties of graphs
• Boundary properties of factorial classes of graphs
• Clique-width for hereditary graph classes
• Deciding the Bell number for hereditary graph properties
• The structure and the number of \(P_7\)-free bipartite graphs
• Clique-width and well-quasi-ordering of triangle-free graph classes
• The structure and the number of \(P_7\)-free bipartite graphs
• A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width
• Succinct data structure for path graphs
• Small but unwieldy: a lower bound on adjacency labels for small classes
• Word-representable graphs and locality of words

This page was built for publication: Clique-width and the speed of hereditary properties

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