2
$\begingroup$

Accoring to Wolfram|Alpha, Georges Graph

$\hskip1in$ enter image description here

is 3-edge colorable. Does anybody have a actual 3-edge coloring in form of three sub-matrices of the adjacence matrix: $$A_1+A_2+A_3=A $$

I tried to get them along the lines given here without success...

EDIT: Some further properties of Georges Graph are:

asymmetric | bicolorable | biconnected | bicubic | bipartite | bridgeless | class 1 | connected | cubic | cyclic | local | noncayley | noneulerian | nonhamiltonian | nonplanar | perfect | perfect matching | regular | square-free | traceable | triangle-free | weakly regular

Maybe this helps someone to help me...

$\endgroup$
1
$\begingroup$

Every 3 edge coloring of a graph will have the adjacency matrix property you seek. Let $c(uv)=i$, then $a_{uv}=1$ in $A_i$. In other words, the coloring induces a partition of the edges.

$\endgroup$
  • $\begingroup$ ...can you give an actual example for a coloring? $\endgroup$ – draks ... Jan 26 '15 at 23:03
  • $\begingroup$ Off the top of my head, no. But I would start by trying to find a spanning cycle, which you may or may not be able to do. If one exists, apply an alternating coloring to that cycle. The remaining edges should be able to colored the third color. Another strategy might be to look for a maximal matching and color it 1, then look for another maximal matching and color it 2, with the remaining edges colored 3. $\endgroup$ – Laars Helenius Jan 26 '15 at 23:17
  • $\begingroup$ If by spanning cycle you mean a Hamilton cycle, I can say the Georges graph doesn't have one. $\endgroup$ – draks ... Jan 26 '15 at 23:26
  • $\begingroup$ OK. Then go with my second strategy. Start finding maximal matchings. $\endgroup$ – Laars Helenius Jan 26 '15 at 23:27
  • $\begingroup$ Concerning your idea about matchings it might be helpful to know that Georges Grah is bipartite. Do you know how to use König's Theorem? $\endgroup$ – draks ... Jan 26 '15 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.