
Summary: We give nontrivial bounds for the inductiveness or degeneracy of power graphs \(G^{k}\) of a planar graph \(G\). This implies bounds for the chromatic number as well, since the inductiveness naturally relates to a greedy algorithm for vertex-coloring the given graph. The inductiveness moreover yields bounds for the choosability of the graph. We show that the inductiveness of a square of a planar graph \(G\) is at most \(\lceil 9\Delta /5 \rceil\), for the maximum degree \(\Delta\) sufficiently large, and that it is sharp. In general, we show for a fixed integer \(k\geq 1\) the inductiveness, the chromatic number, and the choosability of \(G^{k}\) to be \(O(\Delta^{\lfloor k/2 \rfloor})\), which is tight.
Coloring of graphs and hypergraphs, Graph algorithms (graph-theoretic aspects), radio coloring, distance-2 coloring
Coloring of graphs and hypergraphs, Graph algorithms (graph-theoretic aspects), radio coloring, distance-2 coloring
| citations 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). | 80 | |
| 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. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
