Clustering powers of sparse graphs
type: Item
instance of: scholarly article
title: Clustering powers of sparse graphs
zbMATH Open document ID: 1451.05131
DOI: 10.37236/9417
author: J. Nešetřil
author: P. Ossona de Mendez
author: Michał Pilipczuk
author: Xuding Zhu
published in: The Electronic Journal of Combinatorics
publication date: 2020-11-05T00:00:00Z
full work available at URL: https://arxiv.org/abs/2003.03605
review text: Summary: We prove that if \(G\) is a sparse graph -- it belongs to a fixed class of bounded expansion \(\mathcal{C}\) -- and \(d\in \mathbb{N}\) is fixed, then the \(d\)th power of \(G\) can be partitioned into cliques so that contracting each of these clique to a single vertex again yields a sparse graph. This result has several graph-theoretic and algorithmic consequences for powers of sparse graphs, including bounds on their subchromatic number and efficient approximation algorithms for the chromatic number and the clique number.
Mathematics Subject Classification ID: 05C42
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 7270343
zbMATH Keywords: approximation algorithms
zbMATH Keywords: chromatic number
zbMATH Keywords: clique number.
MaRDI profile type: Publication
OpenAlex ID: W3095903540
arXiv ID: 2003.03605
cites work: The subchromatic number of a graph
cites work: The Chromatic Number of Graph Powers
cites work: Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
cites work: Q5090476
cites work: First-Order Interpretations of Bounded Expansion Classes
cites work: Q4625695
cites work: On the generalised colouring numbers of graphs that exclude a fixed minor
cites work: Orderings on graphs and game coloring number
cites work: On low rank-width colorings
cites work: Hardness Results and Efficient Algorithms for Graph Powers
cites work: Tree-depth, subgraph coloring and homomorphism bounds
cites work: Grad and classes with bounded expansion. I: Decompositions
cites work: Grad and classes with bounded expansion. II: Algorithmic aspects
cites work: On nowhere dense graphs
cites work: Sparsity. Graphs, structures, and algorithms
cites work: Polynomial bounds for centered colorings on proper minor-closed graph classes
cites work: Colouring graphs with bounded generalized colouring number
description: scientific article