1
$\begingroup$

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.)

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Casteels
    Jun 20, 2013 at 0:26
  • $\begingroup$ 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. $\endgroup$ Jun 20, 2013 at 1:46

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.