MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given that a 3-regular multigraph is 3-edge-colorable, is there an expression for how many 3-edge-colorings exist?

(For example, if a 2-regular multigraph is 2-edge-colorable, there are $2^k$ 2-edge-colorings where $k$ is the number of cycles.)

share|cite|improve this question
I'd be surprised if there exists a clean general formula like 2^k, but given the graph, the number can certainly be calculated since a proper 3-edge-coloring using colors $\{(0,1),(1,0),(1,1)\}\subset \mathbb{Z}_2\times\mathbb{Z}_2$ is also known as a nowhere-zero $\mathbb{Z}_2\times\mathbb{Z}_2$-flow, and there is a classical contraction-deletion formula to calculate the total number of nowhere-zero $\mathbb{Z}_2\times\mathbb{Z}_2$-flows. (You could also use the Tutte polynomial.) Anyways, See Bondy and Murty, iirc. – Casteels Jun 20 '13 at 0:26
The chromatic polynomial has a contraction-deletion recurrence which you can apply to the linegraph to get edge colourings. It won't be feasible except on small sizes. – Brendan McKay Jun 20 '13 at 1:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.