Clustering powers of sparse graphs

DOI10.37236/9417zbMath1451.05131arXiv2003.03605OpenAlexW3095903540MaRDI QIDQ2209886

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

Publication date: 5 November 2020

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberapproximation algorithmsclique number.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Density (toughness, etc.) (05C42)

Related Items (4)

Rainbow independent sets on dense graph classes ⋮ Bounding generalized coloring numbers of planar graphs using coin models ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs ⋮ From \(\chi\)- to \(\chi_p\)-bounded classes

Cites Work

• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Colouring graphs with bounded generalized colouring number
• The subchromatic number of a graph
• Orderings on graphs and game coloring number
• Polynomial bounds for centered colorings on proper minor-closed graph classes
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• On nowhere dense graphs
• Tree-depth, subgraph coloring and homomorphism bounds
• The Chromatic Number of Graph Powers
• First-Order Interpretations of Bounded Expansion Classes
• Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
• Hardness Results and Efficient Algorithms for Graph Powers
• On low rank-width colorings
• On the generalised colouring numbers of graphs that exclude a fixed minor

This page was built for publication: Clustering powers of sparse graphs