For p = d/n the r-th power has maximum degree ~ log n over (r+1)-fold log and chromatic number sandwiched between the maximum degrees of the floor(r/2) and (r-1) powers plus one (equality at r=2); for d = omega(log n) up to n^{1/r-Omega(1)} the chromatic number is Theta(d^r / log d).
List Colouring Squares of Planar Graphs
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
In 1977, Wegner conjectured that the chromatic number of the square of every planar graph $G$ with maximum degree $\Delta\ge8$ is at most $\bigl\lfloor\frac32\Delta\bigr\rfloor+1$. We show that it is at most $\frac32 \Delta (1+o(1))$ (where the $o(1)$ is as $\Delta\to+\infty$), and indeed that this is true for the list chromatic number and for more general classes of graphs.
citation-role summary
background 1
citation-polarity summary
fields
math.CO 2roles
background 1polarities
background 1representative citing papers
citing papers explorer
-
Coloring powers of random graphs
For p = d/n the r-th power has maximum degree ~ log n over (r+1)-fold log and chromatic number sandwiched between the maximum degrees of the floor(r/2) and (r-1) powers plus one (equality at r=2); for d = omega(log n) up to n^{1/r-Omega(1)} the chromatic number is Theta(d^r / log d).
- Coloring, List Coloring, and Painting Squares of Graphs (and other related problems)