A color-avoiding approach to subgraph counting in bounded expansion classes

DOI10.1007/S00453-023-01096-1arXiv2001.05236OpenAlexW2999223781MaRDI QIDQ6174815

Blair D. Sullivan, Felix Reidl

Publication date: 17 August 2023

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

sparse graphssubgraph countingbounded expansionstrong coloring numberweak coloring number

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

Hardness of the generalized coloring numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Colouring graphs with bounded generalized colouring number
• Orderings on graphs and game coloring number
• Constant-factor approximation of the domination number in sparse graphs
• Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
• Grad and classes with bounded expansion. I: Decompositions
• On nowhere dense graphs
• Parametrized complexity theory.
• Colouring and Covering Nowhere Dense Graphs
• A Dynamic Data Structure for Counting Subgraphs in Sparse Graphs
• Enumeration of monadic second-order queries on trees
• Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
• Hyperbolicity, Degeneracy, and Expansion of Random Intersection Graphs
• Understanding the Complexity of Induced Subgraph Isomorphisms
• The Parameterized Complexity of Counting Problems
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
• On weighted sublinear separators

This page was built for publication: A color-avoiding approach to subgraph counting in bounded expansion classes