Determining Factorial Speed Fast

2026/02/27 by Zhidan Feng, Henning Fernau, Pamela Fleischmann +2 · 1 voice · 1 citation
Computer Science · #cs.DM

paper · pdf · doi:10.48550/arxiv.2602.24064

Abstract

The speed of a graph class \cal G measures how many labeled graphs on n vertices one can find in \cal G. This graph class complexity function is explicitly provided on graphclasses.org. However, for many graph classes, their speed status is classified as unknown. In this paper, w\shortversionWe show that any graph class representable by a finite binary language has at most factorial speed, meaning that its speed function behaves like 2^{Θ(nlog n)}, and we use this criterion to classify many graph classes whose speed was previously unknown as factorial. As a consequence, inclusions between several graph classes can now be seen to be proper. We also prove that k-letter graphs have exponential speed, i.e., the speed function lies in 2^Θ(n).

Citations

• Representation Number of Word-Representable Split Graphs
• Generalized Word-Representable Graphs
• On semi-transitive orientability of circulant graphs
• The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
• Word-representability of split graphs generated by morphisms
• On the Lettericity of Paths
• The Threshold Dimension of a Graph
• Representing split graphs by words
• On semi-transitive orientability of Kneser graphs and their complements
• On operations preserving semi-transitive orientability of graphs
• A Comprehensive Introduction to the Theory of Word-Representable Graphs
• On the representation number of a crown graph
• On the representation number of a crown graph
• Colourability and word-representability of near-triangulations
• Word-Representability of Face Subdivisions of Triangular Grid Graphs
• On graphs with representation number 3
• New results on word-representable graphs
• The Maximum Clique Problem in Multiple Interval Graphs
• Cubicity, Degeneracy, and Crossing Number
• A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs
• Boxicity and Poset Dimension
• Chordal Bipartite Graphs with High Boxicity
• Boxicity of Leaf Powers
• On Restrictions of Balanced 2-Interval Graphs
• Covering and coloring polygon-circle graphs
• Planar graphs and poset dimension
• The Complexity of the Partial Order Dimension Problem

Cited by

• On Languages Describing Large Graph Classes

Discussions

• Zhidan Feng, Henning Fernau, Pamela Fleischmann, Philipp Kindermann, Silas Cato Sacher: Determining Factorial Speed Fast https://arxiv.org/abs/2602.24064 https://arxiv.org/pdf/2602.24064 https://arxiv [bsky, 0 points, 0 comments]

Related

• On the speed of algebraically defined graph classes
• Implicit Representations and Factorial Properties of Graphs
• Graph parameters, implicit representations and factorial properties
• Graph parameters, Ramsey theory and the speed of hereditary properties
• Faster exponential-time algorithms in graphs of bounded average degree