Neighborhood complexity and kernelization for nowhere dense classes of graphs

DOI10.4230/LIPIcs.ICALP.2017.63zbMath1441.68176arXiv1612.08197MaRDI QIDQ5111394

Roman Rabinovich, Kord Eickmeyer, Michał Pilipczuk, Sebastian Siebertz, Stephan Kreutzer, Archontia C. Giannopoulou, O-joung Kwon

Publication date: 27 May 2020

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

zbMATH Keywords

dominating setparameterized complexitykernelizationnowhere dense graphsgraph structure theory

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (24)

Improved bounds for weak coloring numbers ⋮ Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs ⋮ On the parameterized complexity of reconfiguration of connected dominating sets ⋮ Coloring and Covering Nowhere Dense Graphs ⋮ Reconfiguration on nowhere dense graph classes ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ On quasi-planar graphs: clique-width and logical description ⋮ Neighbourhood complexity of graphs of bounded twin-width ⋮ Bounding generalized coloring numbers of planar graphs using coin models ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Unnamed Item ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Unnamed Item ⋮ Bidimensionality and Kernels ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness ⋮ Constant round distributed domination on graph classes with bounded expansion

This page was built for publication: Neighborhood complexity and kernelization for nowhere dense classes of graphs