This solves your requirement for even N with N-1 colors in guarantied polynomial time (explained here )

For odd N its only possible with N colors (explained here )

A generalized solution for any N in N colors is explained here.

use strict;
use warnings;
use Data::Dump qw/pp dd/;


# https://perlmonks.org/?node_id=11141490

my $n=8;

die "n must not be odd" if $n%2;


my @nodes = 0 .. $n-1;

my $center = shift @nodes;


sub rotate(\@) {
    my $r = shift @{$_[0]};
    push @{$_[0]},$r
}

sub get_edges {
    my @verts = @_;
    my $left  = $#verts/2;
    my @res = map [ $verts[$_-1], $verts[-$_] ], 1..$left;
    return [@res,[$center,$verts[$left]]];
}

sub get_matrix{
    my (@colored) = @_;
    my @inc_matrix;
    while ( my ($color,$color_set) = each @colored ) {
        for my $edge (@$color_set) {
            my ($v0,$v1) = @$edge;
            $inc_matrix[ $v0 ][ $v1 ] = $color;
            $inc_matrix[ $v1 ][ $v0 ] = $color;
        }
    }
    return \@inc_matrix;
}

my @colored;
for(@nodes){
    #pp \@nodes;
    push @colored, get_edges(@nodes);
    rotate(@nodes);
}

pp \@colored;


pp get_matrix(@colored);

[download]
OUTPUT: 
[
  [[1, 7], [2, 6], [3, 5], [0, 4]],
  [[2, 1], [3, 7], [4, 6], [0, 5]],
  [[3, 2], [4, 1], [5, 7], [0, 6]],
  [[4, 3], [5, 2], [6, 1], [0, 7]],
  [[5, 4], [6, 3], [7, 2], [0, 1]],
  [[6, 5], [7, 4], [1, 3], [0, 2]],
  [[7, 6], [1, 5], [2, 4], [0, 3]],
]
[
  [undef, 4, 5, 6, 0 .. 3],
  [4, undef, 1, 5, 2, 6, 3, 0],
  [5, 1, undef, 2, 6, 3, 0, 4],
  [6, 5, 2, undef, 3, 0, 4, 1],
  [0, 2, 6, 3, undef, 4, 1, 5],
  [1, 6, 3, 0, 4, undef, 5, 2],
  [2, 3, 0, 4, 1, 5, undef, 6],
  [3, 0, 4, 1, 5, 2, 6],
]

[download]

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery

In reply to Re: Graph labeling problem by LanX
in thread Graph labeling problem by baxy77bax

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.