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)

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