Assertion: graph's number | /r/HasProperty | proportional
Facets:
value: to δ.
type: OTHER
value: to δ2
type: OTHER
value: in the worst case
type: TEMPORAL
Source sentences:
text: Although the chromatic number of the square of a nonplanar graph with maximum degree Δ may be proportional to Δ2 in the worst case, it is smaller for graphs of high girth, being bounded by O(Δ2/log Δ) in this case.
text: More generally, for any graph with degeneracy d and maximum degree Δ, the degeneracy of the square of the graph is O(dΔ), so many types of sparse graph other than the planar graphs also have squares whose chromatic number is proportional to Δ.