Geodesic
Clustering powers of sparse graphs
The electronic journal of combinatorics, Tome 27 (2020) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/9417
Classification : 05C42, 05C85, 05C15
Mots-clés : approximation algorithms, chromatic number, clique number.

Jaroslav Nešetřil    ; Patrice Ossona de Mendez    ; Michał Pilipczuk  1   ; Xuding Zhu 

1 University of Warsaw 
@article{10_37236_9417,
     author = {Jaroslav Ne\v{s}et\v{r}il and Patrice Ossona de Mendez and Micha{\l} Pilipczuk and Xuding Zhu},
     title = {Clustering powers of sparse graphs},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {4},
     doi = {10.37236/9417},
     zbl = {1451.05131},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9417/}
}
TY  - JOUR
AU  - Jaroslav Nešetřil
AU  - Patrice Ossona de Mendez
AU  - Michał Pilipczuk
AU  - Xuding Zhu
TI  - Clustering powers of sparse graphs
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9417/
DO  - 10.37236/9417
ID  - 10_37236_9417
ER  - 
%0 Journal Article
%A Jaroslav Nešetřil
%A Patrice Ossona de Mendez
%A Michał Pilipczuk
%A Xuding Zhu
%T Clustering powers of sparse graphs
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9417/
%R 10.37236/9417
%F 10_37236_9417
Jaroslav Nešetřil; Patrice Ossona de Mendez; Michał Pilipczuk; Xuding Zhu. Clustering powers of sparse graphs. The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/9417

Cité par Sources :