Coloring the square of graphs whose maximum average degree is less than 4

The square G2G2 of a graph GG is the graph defined on V(G)V(G) such that two vertices uu and vv are adjacent in G2G2 if the distance between uu and vv in GG is at most 2. The maximum average degree   of GG, mad(G)mad(G), is the maximum among the average degrees of the subgraphs of GG.It is known in Bonamy et al. (2014) that there is no constant CC such that every graph GG with mad(G)<4mad(G)<4 has χ(G2)≤Δ(G)+Cχ(G2)≤Δ(G)+C. Charpentier (2014) conjectured that there exists an integer DD such that every graph GG with Δ(G)≥DΔ(G)≥D and mad(G)<4mad(G)<4 has χ(G2)≤2Δ(G)χ(G2)≤2Δ(G). Recent result in Bonamy et al. (2014) [2] implies that χ(G2)≤2Δ(G)χ(G2)≤2Δ(G) if mad(G)<4−1c with Δ(G)≥40c−16Δ(G)≥40c−16.In this paper, we show for an integer c≥2c≥2, if mad(G)<4−1c and Δ(G)≥14c−7Δ(G)≥14c−7, then χℓ(G2)≤2Δ(G)χℓ(G2)≤2Δ(G), which improves the result in Bonamy et al. (2014) [2]. We also show that for every integer DD, there is a graph GG with Δ(G)≥DΔ(G)≥D such that mad(G)<4mad(G)<4, and χ(G2)=2Δ(G)+2χ(G2)=2Δ(G)+2, which disproves Charpentier’s conjecture. In addition, we give counterexamples to Charpentier’s another conjecture in Charpentier (2014), stating that for every integer k≥3k≥3, there is an integer DkDk such that every graph GG with mad(G)<2kmad(G)<2k and Δ(G)≥DkΔ(G)≥Dk has χ(G2)≤kΔ(G)−kχ(G2)≤kΔ(G)−k.