Update: This answer is obsoleted by my other answer, with fully polylogarithmic bounds from appropriate references.
On second thought, there's no need to reveal the Merkle tree gradually, so the lower communication version needs no extra rounds. The communication steps are
- The prover P randomizes its coloring, turns it into a (salted) Merkle tree, and sends the root to the verifier V.
- V picks a random edge $e$ and sends it to P.
- P sends the Merkle tree paths from the root to each endpoint of $e$ to V.
This gives $O(be \log n \log (1/p))$ communication over $O(1)$ rounds.
Update: Here are details of the Merkle tree construction. For simplicity, expand the graph to have exactly $2^a$ vertices by adding a few disconnected nodes (these do not effect three colorability or zero knowledge). Assume a secure hash function taking any size input and producing $b$-bit outputs. For each Merkle tree, the prover chooses $2^{a+1}-1$ random $b$-bit nonces, one for each leaf and nonleaf of the binary tree. At the leaves, we hash the color concatenated with the nonce to produce the leaf's value. At each nonleaf, we hash the two child value with the nonleaf's nonce to produce the nonleaf's value.
In the first round, the prover sends only the root value, which provides no information since it is hashed with the root's nonce. In the third round, no information is conveyed about any unexpanded node in the binary tree, since such a node was hashed with a nonce at that node. Here I am assuming the prover and verifier are both computationally bounded and cannot break the hash.
Edit: Thanks to Ricky Demer for pointing out the missing factor of $e$.