The "message" would have to be each vertex's color, separately, rather than the entire graph's coloring at once. Then when the verifier requests the edge for this round, the prover reveals those the commitments for the two vertices on that edge and only those two.

Since the prover doesn't know which edge will be selected and has to commit one color to each vertex, inspecting one random edge per round is enough. They either committed to a 3-coloring and any edge is valid, or they didn't and there's at least one edge we could pick to reject them. The rest of the graph doesn't need to be revealed for us to either gain confidence that they have a coloring or know for certain they do not.