
arXiv: 2003.03605
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.
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), clique number., [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Coloring of graphs and hypergraphs, chromatic number, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Density (toughness, etc.), Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), approximation algorithms, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), clique number., [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Coloring of graphs and hypergraphs, chromatic number, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Density (toughness, etc.), Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), approximation algorithms, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
