Take the 2-minute tour ×
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:

  • $A_1+A_2+A_3=A \tag{1}\label{a}$
  • $A_k^2=1, \tag{2}\label{b} $

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|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 en.wikipedia.org/wiki/Snark_%28graph_theory%29 –  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 cstheory.stackexchange.com/questions/2578/… , 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.