Vertex Ranking of Degenerate Graphs
John Iacono Piotr Micek Pat Morin Bruce Reed


More Asymmetry Yields Faster Matrix Multiplication
    
  
  Josh AlmanColumbia University. . Supported in part by NSF Grant CCF-2238221 and a grant from the Simons Foundation (Grant Number 825870 JA).
  Ran DuanInstitute for Interdisciplinary Information Sciences, Tsinghua University. .
  Virginia Vassilevska WilliamsMassachusetts Institute of Technology. . Supported by NSF Grant CCF-2330048, BSF Grant 2020356 and a Simons Investigator Award. This work was done in part while the author was visiting the Simons Institute for the Theory of Computing.
  
  
  Yinzhan XuMassachusetts Institute of Technology. . Partially supported by NSF Grant CCF-2330048, BSF Grant 2020356 and a Simons Investigator Award. This work was done in part while the author was visiting the Simons Institute for the Theory of Computing.
  Zixuan XuMassachusetts Institute of Technology. .
  Renfei ZhouInstitute for Interdisciplinary Information Sciences, Tsinghua University. .
  

    
================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




  An ℓ-vertex-ranking of a graph G is a colouring of the vertices of G with integer colours so that in any connected subgraph H of G with diameter at most ℓ, there is a vertex in H whose colour is larger than that of every other vertex in H.  The ℓ-vertex-ranking number, (G), of G is the minimum integer k such that G has an ℓ-vertex-ranking using k colours.  We prove that, for any fixed d and ℓ, every d-degenerate n-vertex graph G satisfies (G)= O(n^1-2/(ℓ+1)log n) if ℓ is even and (G)= O(n^1-2/ℓlog n) if ℓ is odd. The case ℓ=2 resolves (up to the log n factor) an open problem posed by <cit.> and the cases ℓ∈{2,3} are asymptotically optimal (up to the log n factor).





§ INTRODUCTION


An ℓ-vertex-ranking of a graph G is a colouring of the vertices of G with integer colours so that in any connected subgraph H of G with diameter at most ℓ, there is a vertex in H whose colour is larger than that of every other vertex in H.  The ℓ-vertex-ranking number (G) is the minimum integer k such that G has an ℓ-vertex-ranking φ:V(G)→{1,…,k}. The ℓ-vertex-ranking number of a graph class 𝒢 is (𝒢):=sup{(G):G∈𝒢}.

When ℓ=1, a colouring is a 1-vertex-ranking if and only if it is a proper colouring of G, so χ(G)=1(G) and, for any ℓ≥ 1, χ(G)≤(G).  Besides the case ℓ=1, two special cases have received extra attention.  When ℓ=∞, ∞(G) is equal to the vertex ranking number, the centered chromatic number, and the treedepth of G
<cit.>,
which plays a central role in the theory of sparsity  <cit.>.
At the other extreme, when ℓ=2, a 2-vertex-ranking of G is also known as a restricted star colouring <cit.> or a unique superior colouring of G <cit.>.  Previous results for ℓ=2 and fixed ℓ≥ 2 are summarized in <ref>.



The current work is motivated by the gap between the upper and lower bounds for 2(G) for d-degenerate graphs G. For fixed d≥ 2, the upper bound is O(√(n)), while the lower bound is Ω(n^1/3). Closing this gap is stated explicitly as an open problem by <cit.> and <cit.>. Our first contribution solves
this problem, up to a logarithmic factor.


  For any positive integer d there exists a constant c:=c(d) such that, for every integer n≥ d, every n-vertex d-degenerate graph G satisfies 2(G)≤ cn^1/3log n.


<Ref> is an immediate consequence of the following more general upper bound for the ℓ-vertex-ranking number of d-degenerate graphs.


  For any positive integers d and ℓ there exists a constant c:=c(d,ℓ) such that, for every integer n≥ d, every n-vertex d-degenerate graph G satisfies
  
    (G)≤ c n^log n
        = 
          cn^1-2/ℓlog n    if ℓ is odd
    
          cn^1-2/ℓ+1log n    if ℓ is even.


<Ref> exhibits a parity phenomenon one encounters when counting the number of paths of length ℓ in a d-degenerate graph of maximum-degree Δ. Because of this, the bound in <ref> is the same for ℓ=2k and ℓ=2k+1, for any positive integer k.  One might think that this is just an artifact of the proof technique and that the bound for even values of ℓ is not tight.  However, <cit.> proved the existence of 2-degenerate n-vertex graphs with 2(G)∈Ω(n^1/3) and <ref> (with ℓ=2) matches this lower bound to within a logarithmic factor.  Since 3(G)≥2(G) for any graph G, it also matches this bound when ℓ=3.  Thus, <ref> is tight (up to a log n factor) for ℓ=2 and ℓ=3, leading us to suspect that it is tight for any fixed ℓ.


Like the upper bound on 2(G) in <cit.>, <ref> follows quickly from a theorem about graphs that are both d-degenerate and have maximum-degree Δ. For such graphs, we prove:


  For all positive integers d and ℓ≥ 2 there exists a constant c:=c(d,ℓ) such that, for every integer Δ≥ d and every integer n≥Δ, every n-vertex d-degenerate graph G of maximum-degree at most Δ satisfies
  
    (G)≤ cΔ^⌊ℓ/2⌋-1/2log^5/4 n
        =
        cΔ^ℓ/2-1log^5/4 n    if ℓ is odd.
    
        cΔ^ℓ/2-1/2log^5/4 n    if ℓ is even.

  Furthermore, if Δ^⌊ℓ/2⌋-1≥log n then (G)≤ cΔ^⌊ℓ/2⌋-1/2log n.


<Ref> follows from <ref>, by the following easy argument:  Let S be the set of vertices in G having degree at least Δ, for some carefully chosen value of Δ.  Since G is d-degenerate, it has at most dn edges, so the total degree of all vertices in G is at most 2dn, so |S|≤ 2dn/Δ.  Now apply <ref> to the graph G-S which is d-degenerate and has maximum-degree Δ to obtain a colouring φ:V(G-S)→{1,…,k}.  Finally, colour every vertex in S with a distinct colour larger than k.  In this way, the total number of colours used is k + |S|≤ cΔ^⌊ℓ/2⌋-1/2log^5/4 n + 2dn/Δ. Choosing Δ to balance these two quantities yields <ref>.  This argument is presented in a little more detail at the end of <ref>.













§ PRELIMINARIES


For any standard graph-theoretic terminology and notation not defined here, we use the same conventions used in the textbook by <cit.>.  A graph G has vertex set V(G) and edge set E(G).  For any S⊆ V(G), G[S] denote the subgraph of G induced by the vertices in S.  For any vertex v of G, N_G(v):={w:vw∈ E(G)} and _G(v):=|N_G(v)|.  For an integer ℓ, G^ℓ denotes the graph with vertex set V(G) that contains an edge vw if and only if some path in G with at most ℓ edges contains both v and w.

The following alternative definition of ℓ-vertex-ranking turns out to be more convenient for proofs and is what we will use from this point on.

  A vertex colouring φ:V(G)→{1,…,k} of a graph G is an ℓ-vertex ranking of G if and only if, for each path v_0,…,v_r in G with at most ℓ edges, φ(v_0)≠φ(v_r) or max{φ(v_1),…,φ(v_r-1)}>φ(v_0).


For a directed graph G, we write vw to denote the directed edge with source v and target w.  For a vertex v in a directed graph G, N^+_G(v):={w∈ V(G):vw∈ E(G)} denotes the set of out-neighbours of v and N^-_G(v):={u∈ V(G):uv∈ E(G)} denotes the set of in-neighbours of v, ^+_G(v):=|N^+_G(v)| is the out-degree of v, and ^-_G(v):=|N^-_G(v)| is the in-degree of v. We also define N^+_G[v]:={v}∪ N^+_G(v) and N^-_G[v]:={v}∪ N^-_G(v) to be the closed out- and in-neighbourhoods of v, respectively.

We repeatedly make use of the following foklore result:


  If an undirected graph G has an orientation in which each vertex has out-degree at most d, then G is 2d-degenerate.



  For any S⊆ V(G), the orientation shows that the induced subgraph G[S] contains at most d|S| edges and therefore the total degree of all vertices in G[S] is at most 2d|S|.  Therefore, for any S⊆ V(G), the induced graph G[S] has a vertex of degree at most 2d.


An undirected path Π in a graph G is a tree with exactly two leaves whose edges are all edges of G. The leaves of Π are called the endpoints of Π. The length of Π is the number of edges in Π, which is exactly one less than the number of vertices.  With a slight abuse of notation, we write x_0,…,x_r to denote a length-r undirected path Π where x_0 and x_r are the endpoints of Π and Π contains the edge x_i-1x_i for each i∈{1,…,r}.  Note that each undirected path Π:=x_0,…,x_r in G corresponds to exactly two paths x_0,x_1,…,x_r and x_r,x_r-1,…,x_0 in G.

For a graph G, let 𝒫_ℓ(G) denote the set of all undirected paths of length at most ℓ in G.  The set 𝒫_ℓ(G) is critical for us since, by <ref>, this is precisely the set of paths that need to be considered to determine if a vertex-colouring φ of G is an ℓ-vertex-ranking.  The following lemma shows that the paths in 𝒫_ℓ(G) can be mapped onto their endpoints in such a way that no endpoint receives too many paths.  Its proof uses a technique introduced by Cairns to upper bound the number of length-ℓ paths in planar graphs (see also <cit.>).


  For any integers d≥ 2, ℓ≥ 2, Δ≥ d and any
  graph G of maximum-degree Δ that has an orientation of maximum out-degree d there exists a mapping ρ:𝒫_ℓ(G)→ V(G) such that
  [(i)]
    
  * ρ(Π) is an endpoint of Π for each Π∈𝒫_ℓ(G); and
    
  * |ρ^-1(v)| ≤ 2^ℓ+1d^⌈ℓ/2⌉Δ^⌊ℓ/2⌋ for each v∈ V(G).
  



  Fix some orientation of G of maximum out-degree d. For each Π∈𝒫_ℓ(G) let x_0,…,x_r be one of the two paths in G that corresponds to Π, chosen so that the edge x_i-1x_i is oriented from away from x_i-1 and towards x_i for at least half the indices i∈{1,…,r}.  When x_i-1x_i is oriented away from x_i-1, we call it a downstream edge of Π. Otherwise we call x_i-1x_i an upstream edge of Π. In other words, we choose the endpoint x_0 so that at least half the edges of Π are downstream edges, and we set ρ(Π):=x_0.  Observe that the path x_0,…,x_r can be uniquely reconstructed from the following information:
  [(a)]
    
  * A sequence b_1,…,b_r of r bits, where b_i=1 if x_i-1x_i is a downstream edge of Π and b_i=0 if x_i-1x_i is an upstream edge of Π.
    
  * A sequence δ_1,…,δ_r of integers, where δ_i∈{1,…,d} if b_i=1 and δ_i∈{1,…,Δ} if b_i=0.  The integer δ_i uniquely identifies the neighbour x_i of x_i-1 so that, starting at x_0 we can uniquely reconstruct the path x_0,…,x_r which uniquely identifies the undirected path Π.
  
  The number of choices for (<ref>) is 2^r.  Since (<ref>) has at least as many 1-bits as 0-bits, the number of choices for (<ref>) is at most d^⌈ r/2⌉Δ^⌊ r/2⌋.  So the number of paths of length r in ρ^-1(x_0) is at most 2^rd^⌈ r/2⌉Δ^⌊ r/2⌋.  Summing r over 1 to ℓ completes the proof.


Observe that, for each edge vw in G^ℓ there is at least one path in 𝒫_ℓ(G) with endpoints v and w.  For each edge vw of G^ℓ we can select one such representative path Π_vw∈𝒫_ℓ(G).  If we then orient each edge vw of G^ℓ away from ρ(Π_vw) then we get an orientation of G^ℓ in which each vertex has out-degree at most 2^ℓ+1d^⌈ℓ/2⌉Δ^⌊ℓ/2⌋.  Combined with <ref> this gives the following corollary:


  For any integers d≥ 1, Δ≥ d and any d-degenerate graph G of maximum degree Δ, G^ℓ is 2^ℓ+2d^⌈ℓ/2⌉Δ^⌊ℓ/2⌋-degenerate.


In order to obtain the bound in <ref> we need a special version of <ref> that only considers undirected paths v_0,…,v_r∈𝒫_ℓ(G) such that v_0v_1 is directed toward v_0 and v_r-1v_r is directed toward v_r.  For a directed graph G' whose underlying undirected graph is G, let 𝒫_ℓ(G') denote the set of undirected paths x_0,…,x_r in G of length r≤ℓ and such that x_0x_1 is an edge of G' and x_r-1x_r is also an edge of G'.


  For any integers d≥ 2, ℓ≥ 3, Δ≥ d and any
  directed graph G' of maximum degree Δ and maximum out-degree d, there exists a mapping γ:𝒫_ℓ(G')→ V(G') such that
  [(i)]
    
  * γ(Π)∈ V(Π) for each Π∈𝒫; and
    
  * |γ^-1(v)| ≤ 2^ℓd^⌈ℓ/2⌉+1Δ^⌊ℓ/2⌋-1 for each v∈ V(G').
  



  The proof is almost identical to <ref> with two modifications.  If G' contains both edges vw and wv then this edge is considered as a downstream edge no matter which direction it is traversed, since there are at most d options for edges leaving v (one of which is w) and at most d options for edges leaving w (one of which is v).

  For an undirected path Π:=v_0,…,v_r∈𝒫_ℓ(G'), the total number of upstream edges in the path v_1,…,v_r and in the path v_r-1,…,v_0 is at most r-2. (The edge v_r-1v_r is a downstream edge in the first path, v_1v_0 is a downstream edge in the second path, and each of the edges in v_1,…,v_r is upstream in at most one of the two paths.)  Therefore we can choose the endpoint v_0 so that the number of upstream edges in v_1,…,v_r is at most ⌊ (r-2)/2⌋=⌊ r/2⌋-1 and set γ(Π):=v_1. For r≥ 3, Π can then be obtained by taking the union of the paths x_1,x_0 and x_1,x_2,…,x_r.  The first path consists of one downstream edge, so there are at most d options for the first path.  The second path has r-1 edges and at most ⌊ r/2⌋-1 of these are upstream edges, so there are at most 2^r-1d^⌈ r/2⌉Δ^⌊ r/2⌋-1 options for the second path.
   Thus, the number of paths of length r assigned to any vertex is at most 2^r-1d^⌈ r/2⌉+1Δ^⌊ r/2⌋-1 for r≥ 3 (and at most d^r for r∈{1,2}). Again, the proof finish by summing over r in 1,….ℓ.





§ THE PROOF



For a vertex colouring φ:V(G)→ of a graph G, we say that an undirected path Π:=x_0,…,x_r in G is an ℓ-violation of φ if Π has length r≤ℓ and φ(x_0)=φ(x_r)=max{φ(x_0),…,φ(x_r)}.  Observe that φ is an ℓ-vertex-ranking if and only if G contains no ℓ-violations of φ.




  Let G be an n-vertex d-degenerate graph of maximum-degree Δ.  Let S_0:=V(G) and, for each integer i≥ 1, let S_i:={v∈ S_i-1:_G[S_i-1](v)≥ 4d}.  Since G is d-degenerate G[S_i-1] has at most d|S_i-1| edges.  Therefore
  
    2d|S_i-1|≥∑_v∈ S_i-1_G[S_i-1](v)≥ 4d|S_i|  ,

  so |S_i|≤ |S_i-1|/2≤ n/2^i for each i≥ 1.  Let q be the maximum integer such that S_q is non-empty.  Since 1≤ |S_q|≤ n/2^q, q≤log_2 n.  For each i∈{0,…,q}, let L_i:=S_i∖ S_i+1.  (These notations are mnemonics: S_i contains the survivors of round i-1 and L_i is layer i.)

  Let b=1/4 and let k:=Δ^⌊ℓ/2⌋-1/2log^b n, so that our goal is to find an ℓ-vertex-ranking of G using O(klog n) colours. We compute our colouring using a two phase algorithm. In the first phase we use a sequence of pairwise-disjoint colour palettes Φ_0,…,Φ_q, each of size 2k, such that for each 1≤ i < j≤ q, every colour in Φ_i is less than every colour in Φ_j.  We will use the colours in Φ_i to colour the vertices in L_i, for each i∈{0,…,q}.  The total number of colours used in this phase is 2k(q+1)≤ 2k(1+log n)= O(klog n).  The first phase colouring φ:V(G)→Φ_0∪⋯∪Φ_q may have some ℓ-violations that will be eliminated by re-colouring some vertices in the second phase using an additional palette Φ_q+1 of size O(klog n).

  Let 𝒫 contain all the undirected paths x_0,…,x_r in 𝒫_ℓ(G) such that x_0 and x_r are in the same layer L_j and {x_1,…,x_r-1}⊆⋃_i=0^j L_i.  Since G is d-degenerate, it has an orientation of maximum out-degree d.  Let ρ:𝒫→ V(G) be the mapping given by <ref>, applied to G, restricted to the paths in 𝒫. (The purpose of the restriction is so that ρ^-1(v) denotes a subset of 𝒫.)  We will say that an undirected path Π:=x_0,…,x_r in 𝒫 is problematic if x_0 and x_r are assigned the same colour in the first phase of the algorithm.

  Although we have not yet completed the description of the first phase colouring procedure, we already know enough to establish the following claim:  Any ℓ-violation Π of the first phase colouring φ is a problematic path in 𝒫.  Indeed, if Π=x_0,…,x_r is an ℓ-violation, then φ(x_0)=φ(x_r)∈Φ_j for some j∈{0,…,q}.  Thus x_0,x_r∈ L_j for some j∈{0,…,q}.  Furthermore, since Π is an ℓ-violation φ(x_0)=max{φ(x_0),…,φ(x_r)}, so no colour in Φ_j+1,…,Φ_q appears at any vertex in x_1,…,x_r-1.  Therefore, {x_1,…,x_r-1}⊆⋃_i=0^j L_i.  Therefore Π∈𝒫.  Since φ(x_0)=φ(x_r), Π is problematic.

  We now describe the first phase colouring algorithm.  Consider the multigraph G^* that, for each vw∈ V(G) contains as many copies of the edge vw as there are undirected paths in 𝒫 with endpoints v and w.  The existence of ρ implies that G^* has an orientation in which each vertex has out-degree O(Δ^⌊ℓ /2⌋).  By <ref>, G^* is O(Δ^⌊ℓ /2⌋)-degenerate.  Label the vertices of G as v_1,…,v_n so that v_i has degree O(Δ^⌊ℓ /2⌋) in G^*[{v_1,…,v_i}]. In other words, for each a∈{1,…,n} the number of paths in 𝒫 with one endpoint at v_a and the other endpoint in {v_1,…,v_a-1} is O(Δ^⌊ℓ /2⌋).  In the first phase, we will colour the vertices one by one in the order v_1,…,v_n.

  Let τ:𝒫→ V(G) be the mapping that maps Π∈𝒫 to v_b if and only if the endpoints of Π are v_a and v_b and a < b.[The two mappings τ and ρ are similar. The difference is that ρ corresponds to some orientation of G^* and τ corresponds to an acyclic orientation of G^*.]  Consider some vertex w∈ L_j.  For each α∈Φ_j, let N_α(w) be the number of paths in τ^-1(w) whose other endpoint (not w) is assigned the colour α. If w=v_b then N_α(w) is completely determined by the colours of v_1,…,v_b-1, so the value of N_α(v_b) is determined after v_b-1 is coloured but before v_b is coloured.  Observe that assigning the colour α to w creates exactly N_α(w) problematic paths, and these are all in τ^-1(w).  Therefore, ∑_α∈Φ_j N_α(w)=|τ^-1(w)|∈ O(Δ^⌊ℓ /2⌋).

  For each vertex w, we choose the colour of w uniformly at random from a subpalette of Φ_i that contains exactly half of the 2k colours in Φ_i.  Specifically, we choose the colour of w from a palette Φ(w)⊂Φ_i that contains k colours α in Φ_i with the smallest N_α(w) values, so that  max{N_α(w):α∈Φ(w)}≤min{N_α(w):α∈Φ_i∖Φ(w)}.  Let M:=cΔ^⌊ℓ/2⌋/k with c sufficiently large so that Mk≥τ^-1(w).
  Then
  
    Mk ≥ |τ^-1(w)|= ∑_α∈Φ_i N_α(w) ≥∑_α∈Φ_i∖Φ(w)N_α(w) ≥ kmax{N_α(w):α∈Φ(w)} .

  Therefore, max{N_α(w):α∈Φ(w)}≤ M is the maximum number of problematic paths in 𝒫 that can be created by colouring w, and M is the maximum number of problematic paths that can be created by colouring any single vertex.  This completes the description of the first-phase colouring φ of G.


  The first phase colouring φ is not yet an ℓ-vertex-ranking.  Our goal now is to study the problematic paths in 𝒫, each of which is a potential ℓ-violation of φ.  For each problematic Π∈𝒫, we will choose a vertex y of Π to recolour in the second round to eliminate the possibility that Π is an ℓ-violation. of φ.  Consider the directed graph G' obtained from G by adding each edge vw if vw∈ E(G), v∈ L_i, w∈ L_j and i≤ j.  (Note that if v and w are in the same layer L_j then both edges vw and vw are present in G'.)  Then G' has maximum out-degree at most 4d and 𝒫_ℓ(G') contains 𝒫. Let γ:𝒫→ V(G) be the result of applying <ref> to G' (and then restricting it to the paths in 𝒫.)  For each problematic path Π∈𝒫, we call the vertex γ(Π) problematic.  We will recolour γ(Π) in order to avoid the potential ℓ-violation at Π.

  Let P be the set of all problematic vertices.  In the second phase, we recolour every vertex in P with a colour in a palette Φ_q+1 of size cklog n + 1 whose colours are all larger than all colours in Φ_0,…,Φ_q.  Since each ℓ-violation of φ contains a vertex in P, this recolouring eliminates all the existing ℓ-violations in φ.  More precisely, after this recolouring any remaining ℓ-violation must have both endpoints whose colour is in Φ_q+1.  So that this never happens, we will ensure that our recolouring is a proper colouring of G^ℓ[P].  By definition, this means that any path in 𝒫_ℓ(G) with both endpoints in P has endpoints of different colours and is therefore not an ℓ-violation.

  By <ref>, G^ℓ is O(Δ^⌊ℓ /2⌋)-degenerate.  Let H be a directed acyclic graph obtained from G^ℓ in which each vertex has out-degree O(Δ^⌊ℓ /2⌋). We want to show that G^ℓ[P] has chromatic number at most cklog n+1.
  To do this, we will show that the maximum out-degree of H[P] is at most cklog n, with high probability.  In fact, we will show something stronger: that every vertex p in H has at most cklog n out-neighbours in P.

  From this point on, we fix some vertex p of H and study the random variable |N_H^+(p)∩ P|.  Instead of focusing on the set P of problematic vertices, we focus instead on problematic paths.  For each problematic vertex y, some path Π in γ^-1(y) is problematic. Therefore,
  
    |N^+_H(p)∩ P| ≤∑_y∈ N^+_H(p)|{Π∈γ^-1(y): Π is problematic}| =: X'_p .

  Each path Π∈𝒫 is problematic with probability at most 1/k since Π becomes problematic precisely when we choose the same colour for w:=τ(Π) that was already chosen for the other endpoint of Π.  Therefore,
  
    (|N^+_H(p)∩ P|)
           ≤1/k∑_y∈ N^+_H(p)|γ^-1(y)| 
       ≤1/k·|N^+_H(p)|· O(Δ^⌊ℓ /2⌋-1) 
       ≤1/k· O(Δ^2⌊ℓ /2⌋-1) 
        = O(Δ^⌊ℓ /2⌋-1/2log^-b n) = O(klog^-2b n)  .

  This is a good sign. If the event set {“Π is problematic”:Π∈𝒫} were mutually independent then it would be a simple matter of applying a Chernoff bound.  Unfortunately this is not the case since, for each vertex w, all of the events in {“Π is problematic”:Π∈τ^-1(w)} are all affected by the choice of colour for w.

  The remainder of the proof is more probability than graph theory.  We will use a tail estimate for sums of independent random variables due to Bernstein that is applicable when these random variables have sufficiently small variance.  The statement of Bernstein's Inequality and the calculations needed to apply it in this context are deferred to the next section. We use the rest of our time here to describe a random variable X_p that stochastically dominates X'_p≥ |N^+_H(p)∩ P| and is a sum of independent random variables.[A random variable X stochastically dominates a random variable Y if (X≥ x) ≥(Y≥ x) for all x∈.]

  For each vertex w of G, let 𝒫_p,w:=τ^-1(w)∩ (⋃_y∈ N^+_H(p)γ^-1(y)) and define
  
    X'_p,w :=|{Π∈𝒫_p,w:Π is problematic}|
         .

  Since each problematic path Π counted by the right-hand-side of <ref> becomes problematic when w:=τ(Π) is coloured, X'_p=∑_w∈ V(G) X'_p,w.

  Suppose w∈ L_j for some j∈{0,…,q}.  For each α∈Φ_j, let N_α(p,w) be the number of paths in 𝒫_p,w that would have become problematic if we had set the colour of w to α. Then ∑_α∈Φ(w) N_α(p,w) ≤∑_α∈Φ_j N_α(p,w) ≤∑_α∈Φ_j N_α(w) = |τ^-1(w)|.

  Let α_1,…,α_k be the colours in Φ(w) ordered so that
  
    N_α_1(p,w) ≥ N_α_2(p,w) ≥⋯≥ N_α_k(p,w)  .

  Then, for each i∈{1,…,k}, iN_α_i(p,w)≤∑_j=1^i N_α_j(p,w) ≤ |τ^-1(w)|, so
  
    N_α_i(p,w)≤|τ^-1(w)|/i=O(Δ^⌊ℓ/2⌋)/i .

  Therefore, regardless of any random choices made before choosing the colour of w and any random choices made after choosing the colour of w, the random variable X'_p,w is dominated by a random variable X_p,w:=min{O(Δ^⌊ℓ/2⌋)/i,M} where i is chosen uniformly in {1,…,k}.

  Therefore, |N_H^+(p)∩ P| is dominated by a sum X_p:=∑_w X_p,w of mutually independent random variables.  In order to apply a concentration result to the random variable X_p, we need to  establish sufficiently strong properties on the individual terms X_p,w.  In the next section, we bound the expectation and variance of each X_p,w so that we can apply Bernstein's Inequality to prove that (X_p≥ cklog n)≤ n^-Ω(c).  Then the union bound implies that (max{X_p:p∈ V(H)}≥ cklog n)≤ n^-Ω(c).  Thus, with high probability, the number of additional colours in Φ_q+1 needed to recolour the vertices of P in the second phase is O(klog n).  Since the total number of colours used in the first phase is O(klog n), we have
  
    (G) = O(k log n) = O(Δ^⌊ℓ/2⌋-1/2log^5/4 n)  .



With the proof of <ref> out of the way, we now show how it implies <ref>.


  Since G is d-degenerate, it has at most dn edges and the sum of its vertex degrees is at most 2dn.  Let Δ:=n^1/(⌊ℓ/2⌋+1/2)log^-x n for some value x to be discussed shortly.  Then the set S:={v∈ V(G):_G(v)≥Δ} has size at most 2dn/Δ=2dn^log^x n.  Since G-S is d-degenerate and has maximum degree Δ, <ref> implies that
  
    (G-S)    ≤ cΔ^⌊ℓ/2⌋-1/2log^5/4 n 
        = cn^⌊ℓ/2⌋-1/2/⌊ℓ/2⌋+1/2log^5/4-x(⌊ℓ/2⌋-1/2) n 
        = cn^log^5/4-x(⌊ℓ/2⌋-1/2) n 
       ≤ cn^log^5/4-x/2 n

  where the last inequality follows from the fact that ⌊ℓ/2⌋-1/2≥ 1/2 for all ℓ≥ 2.  Taking x:=5/6, we get |S|=O(n^log^5/6 n)=O(n^log n) and  (G-S)= O(n^log^5/4-5/12 n)=O(n^log^5/6 n).  We can extend φ to a colouring of G by assigning each vertex in S a distinct colour that is larger than every colour used in the colouring of G-S.  Thus, (G)≤ |S|+(G-S) ≤ O(n^log^5/6 n), which establishes <ref>.  (Note that this argument actually proves a slightly better bound than <ref>.  For ℓ≥ 4, further improvements to the logarithmic factor in <ref> can be obtained using the “Furthermore” clause of <ref>.)










§ BOUNDING THE TAIL OF X_P



We make use of the following inequality of Bernstein <cit.>:


  Let M be a positive number, let X_1,…,X_r be independent random variables such that 0≤ X_i≤ M for each i∈{1,…,r}, and let X:=∑_i=1^r X_i. Then
  
    (X ≥(X)+ t)
          ≤exp(12t^2/∑_i=1^r ((X_i-(X_i))^2)+13Mt)  .


We will apply <ref> to a random variable X:=∑_i=1^r X_i in which each X_i has the following distribution (for some 0≤ x_i≤ kM):

    X_i = 
              M    with probability (1/k)⌊ x_i/M⌋
    
              x_i/j    with probability 1/k for each j∈{⌊ x_i/M⌋+1,…,k}

This is the distribution we get when we choose a uniform j∈{1,…,k} and set X_i:=min{M,x_i/j).  To see how this applies in the proof of <ref>, let r:=n, let {w_1,…,w_n}:=V(G) and, for each i∈{1,…,n}, let x_i:=|τ^-1(w_i)∩(⋃_y∈ N^+_H(p)γ^-1(y))|.  In our setting k=Δ^⌊ℓ/2⌋-1/2log^b n for some b≥ 0,  M=aΔ^⌊ℓ/2⌋/k for some constant a, and t=cklog n for some (sufficiently large) constant c.  The rest of this appendix is devoted to bounding the various quantities that appear in <ref> so that we can show that the right-hand side of <ref> is n^-Ω(c).

Both the maximum value and the sum of x_1,…,x_n are important for us. For the maximum, we have x_i≤|τ^-1(w_i)|= O(Δ^⌊ℓ/2⌋) for all i∈{1,…,n}.  We have already bounded the sum when computing the expectation of |N_H^+(p)∩ P| as follows:

    ∑_i=1^n x_i = ∑_y∈ N^+_H(p) |γ^-1(y)|
      ≤ |N^+_H(p)|· O(Δ^⌊ℓ/2⌋-1)
      ≤ O(Δ^2⌊ℓ/2⌋-1)  .


For each i∈{1,…,n}, we have

    (X_i)
          =(X_i=M)· M + ∑_j=⌊ x_i/M⌋+1^k (X_i=x_i/j)·x_i/j
       ≤x_i/kM· M + 1/k·∑_j=⌊ x_i/M⌋+1^k x_i/j
       ≤x_i/k + 1/k·∑_j=1^k x_i/j
       ≤x_i(2+ln k)/k   (since ∑_j=1^k 1/k≤ 1+ln k)
        = O(x_ilog k/k) 
        = O(x_ilog n/k)
       ,

where the last line comes from the fact that d,Δ≤ n and ℓ∈ O(1).
Therefore,

    ((X_i))^2
          = O((x_ilog n/k)^2) 
        = O(x_i^2log^2 n/k^2) 
        = O(x_i^2log^2 n/Δ^2⌊ℓ/2⌋-1log^2b n) 
        = O(x_ilog^2-2b n/Δ^⌊ℓ/2⌋-1)
          (since x_i=O(Δ^⌊ℓ/2⌋))

Now,

    ((X_i-(X_i))^2)  = 1/k⌊x_i/M⌋·(M-(X_i))^2 + ∑_j=⌊ x_i/M⌋+1^k 1/k(x_i/j-(X_i))^2

We bound the first term on the right hand side of <ref> as follows:

    1/k⌊x_i/M⌋·(M-(X_i))^2
         ≤x_i/kM(M^2 + ((X_i))^2) 
        = M x_i/k + x_i/kM· ((X_i))^2 
       ≤M x_i/k + ((X_i))^2
         (since x_i=|τ^-1(w_i)|≤ Mk)
        = O(Δ^⌊ℓ/2⌋x_i/k^2) + ((X_i))^2
         (by the definition of M)
        = O(x_ilog^-2b n/Δ^⌊ℓ/2⌋-1) + ((X_i))^2
         (by the definition of k)
        = O(x_ilog^2-2b n/Δ^⌊ℓ/2⌋-1)
         (by <ref>, since 2-2b≥ -2b) .

We bound the remaining terms in <ref> as follows:

    ∑_j=⌊ x_i/M⌋+1^k 1/k(x_i/j-(X_i))^2
         ≤∑_j=⌊ x_i/M⌋+1^k 1/k(x_i^2/j^2+((X_i))^2) 
       ≤ ((X_i))^2+1/k∑_j=⌊ x_i/M⌋+1^k x_i^2/j^2
       ≤ ((X_i))^2 +  1/k·Mπ^2x_i^2/6 x_i   (since ∑_j=z^∞1j^2≤π^26z for z≥ 1)
        = ((X_i))^2 + O(Mx_i/k) 
        = O(x_ilog^2-2b n/Δ^⌊ℓ/2⌋-1)
         (as above) .

Therefore

    ((X_i-(X_i))^2) = O(x_ilog^2-2b n/Δ^⌊ℓ/2⌋-1)

for all i∈{1,…,n}.  Recall that ∑_i=1^n x_i = O(Δ^2⌊ℓ/2⌋-1), so

    (X)
      = ∑_i=1^n (X_i)
      = ∑_i=1^n O(x_ilog n/k)
      = O(Δ^2⌊ℓ/2⌋-1log n/k)
      = O(Δ^⌊ℓ/2⌋-1/2log^1-b n)  .

and

    ∑_i=1^r((X_i-(X_i))^2)
      = ∑_i=1^r O(x_ilog^2-2b n/Δ^⌊ℓ/2⌋-1)
      = O(Δ^2⌊ℓ/2⌋-1log^2-2b n/Δ^⌊ℓ/2⌋-1)
      = O(Δ^⌊ℓ/2⌋log^2-2b n)
       .

Then <ref> gives:

    (X≥(X)+t)
          = (X≥(X)+cklog n) 
       ≤exp(-12(cklog n)^2/O(Δ^⌊ℓ/2⌋log^2-2b n) + 13Mcklog n) 
        = exp(-12(cklog n)^2/O(Δ^⌊ℓ/2⌋log^2-2b n +cΔ^⌊ℓ/2⌋log n)))
           (since Mk=O(Δ^⌊ℓ/2⌋))
        = exp(-12(cklog n)^2/O(cΔ^⌊ℓ/2⌋log^2-2b n))     (for c≥ 1 and b≤ 1/2) 
        = exp(-12cΔ^2⌊ℓ/2⌋-1log^2+2b n/O(Δ^⌊ℓ/2⌋log^2-2b n))    (by definition of k)
        = exp(-Ω(cΔ^⌊ℓ/2⌋-1log^4b n)) 
        = n^-Ω(c) ,

provided that b≥ 1/4 or Δ^⌊ℓ/2⌋-1≥log n.
For any fixed c, taking b=1/4 gives

    (X)+t
            = O(Δ^⌊ℓ/2⌋-1/2log^1-b n + klog n) 
        = O(Δ^⌊ℓ/2⌋-1/2(log^1-b n + log^1+b n)) 
        = O(Δ^⌊ℓ/2⌋-1/2log^5/4 n)

Thus, (X≥ cΔ^⌊ℓ/2⌋-1/2log^5/4 n) ≤ n^-Ω(c), which completes the first part of the proof of <ref> for the cases ℓ=2 and ℓ=3.  To complete the “furthermore” clause of the proof we take b=0 and deduce that (X)+t=O(Δ^⌊ℓ/2⌋-1/2log n).




§ ACKNOWLEDGEMENT


Some of this research began during the Third Workshop on Geometry and Graphs (WoGaG 2015), March 8–13, 2015, and resumed during the Second Adriatic Workshop on Graphs and Probability (AWGP 2023), Jun 24–Jul 1, 2023. The authors are grateful to the organizers of both workshops for providing a stimulating and productive work environment.


plainnat




