Hardness of the generalized coloring numbers

DOI10.1016/j.ejc.2023.103709zbMATH Open1548.05114MaRDI QIDQ6614401

Michael Breen-McKay, Brian Lavallee, Blair D. Sullivan

Publication date: 7 October 2024

Published in: European Journal of Combinatorics (Search for Journal in Brave)

zbMATH Keywords

weak \(r\)-coloring number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• A simplified NP-complete satisfiability problem
• Colouring graphs with bounded generalized colouring number
• Characterising bounded expansion by neighbourhood complexity
• Orderings on graphs and game coloring number
• Constant-factor approximation of the domination number in sparse graphs
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Coloring and Covering Nowhere Dense Graphs
• Kernelization and Sparseness: the case of Dominating Set
• The complexity of finding maximum disjoint paths with length constraints
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• Reducibility among Combinatorial Problems
• A color-avoiding approach to subgraph counting in bounded expansion classes

This page was built for publication: Hardness of the generalized coloring numbers