Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm currently trying to implement an algorithm to $3$-colour the edges of cubic graphs. (I want to do this with Matlab's Symbolic toolbox). After restricting to planar graphs to ensure the existence of a solution, I tried the following:

First, I observed that once a colouring is found the adjacency matrix $A$ split into three matrices with the following properties:

  • $\hskip-5.0in A_1+A_2+A_3=A \tag{1}$
  • $\hskip-5.0in A_k^2=1, \tag{2} $

where $1$ is the unit matrix and the idea is related to the concept of $1$-factors I think...

So I tried the following:

  1. I set up matrices $X=(x_{kl})\odot A$, where $\odot$ is the Hadamard product ($Y$ and $Z$ accordingly),
  2. plugged them into $(1)$ and $(2)$,
  3. let the computer solve the set of equations
  4. received some promising results for small dimensions (less than $10$)
  5. and some frustating for larger ones (more than $20$).

I tried to use facts like, all entries in $A_k$ are either $0$ or $1$, so squares of certain variables in $(2)$ could be written as linear terms as well.

So my question is:

Is there a principle problem with this approach? Which other mathematical tricks can I use?

share|cite|improve this question
Have you read about snarks? These are precisely the cubic graphs that are not 3-edge-colorable and hence your problem is in a way equivalent to recognizing snarks. See – Jernej Oct 9 '13 at 10:29
@Jernej I have, and therefore I tried examples where I knew a $3$-edge-colouring in advance, i.e. planar cubic graphs...In other words: No snarks, please... – draks ... Oct 10 '13 at 20:06
You might want to have a look at… , which appears to cover precisely this question. – Steven Stadnicki Nov 20 '13 at 21:14
@StevenStadnicki great link, thanks... – draks ... Nov 20 '13 at 21:16

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.