# can you find the total chromatic number (edge and vertices) of a graph?

I' m trying to find the total chromatic number of a graph and I was wondering if anyone knew how to do this? I have found the edge and vertex chromatic number but am unable to join the 2.

edit retag close merge delete

Sort by » oldest newest most voted

You can solve this problem using mixed linear integer prrogramming, as follows:

• loop over the number n of colors
• for each such n, add n binary variables to each vertex and to each edge: bv[v,c] and be[e,c], where v is a vertex, e is an edge, and 0<=c<=n-1 is an integer. The meaning is: bv[v,c] is 1 iff the vertex v has color c, be[e,c] is 1 iff the edge e has color c.
• for each vertex v, the sum of bv[v,c] for c<=n-1 is equal to 1 (meaning each vertex get exactely one color)
• for each edge, the sum of be[e,c] for c<=n-1 is equal to 1 (meaning each edge get exactly one color)
• for each vertex v, for each c<=n-1, bv[v,c] plus the sum of be[e,c] where e is an edge adjacent to v is at most 1 (coloring condition around vertices)
• for each edge e = (v,w), for each c<=n-1, bv[v,c]+bv[w,c]+be[e,c] is at most 1 (coloring condition around edges)
• try to solve, if you succeed, you get your coloring, if you get an exception, increase n by 1 and iterate

EDIT Here is a possible implementation;

sage: from sage.numerical.mip import MIPSolverException
sage: def total_chromatic_number(G, certificate=False):
....:     nmax = len(G) + len(G.edges()) # trivial upper bound on the number of colors.
....:     for n in range(1,nmax+1):
....:         p = MixedIntegerLinearProgram()
....:         bv = p.new_variable(binary=True)
....:         be = p.new_variable(binary=True)
....:         for v in G.vertices():
....:             p.add_constraint(sum(bv[v,c] for c in range(n)) == 1)
....:         for e in G.edges(labels=False):
....:             p.add_constraint(sum(be[e,c] for c in range(n)) == 1)
....:         for v in G.vertices():
....:             for c in range(n):
....:                 p.add_constraint(bv[v,c] + sum(be[e,c] for e in G.edges_incident(v, labels=False)) <= 1)
....:         for v,w in G.edges(labels=False):
....:             for c in range(n):
....:                 p.add_constraint(bv[v,c] + bv[w,c] + be[(v,w),c] <= 1)
....:         try:
....:             p.solve()
....:             if certificate:
....:                 bv_sol = p.get_values(bv)
....:                 be_sol = p.get_values(be)
....:                 coloration = {}
....:                 for v in G.vertices():
....:                     for c in range(n):
....:                         if bv_sol[v,c] == 1:
....:                             coloration[v] = c
....:                 for e in G.edges(labels=False):
....:                     for c in range(n):
....:                         if be_sol[e,c] == 1:
....:                             coloration[e] = c
....:                 return coloration
....:             else:
....:                 return n
....:         except MIPSolverException:
....:             pass


We can test in on the Petersen graph, and see that its total chromatic number is 4:

sage: G = graphs.PetersenGraph()
sage: total_chromatic_number(G)
4


And get an admissible total coloration:

sage: total_chromatic_number(G, certificate=True)
{0: 0,
1: 1,
2: 3,
3: 0,
4: 1,
5: 3,
6: 0,
7: 0,
8: 2,
9: 2,
(0, 1): 3,
(0, 4): 2,
(0, 5): 1,
(1, 2): 0,
(1, 6): 2,
(2, 3): 2,
(2, 7): 1,
(3, 4): 3,
(3, 8): 1,
(4, 9): 0,
(5, 7): 2,
(5, 8): 0,
(6, 8): 3,
(6, 9): 1,
(7, 9): 3}

more

@tmonteil Thank you for your response. I think I know how to create the constraints but I am confused as to how to do the first 2 points?

( 2016-12-01 07:44:20 -0600 )edit

( 2016-12-20 17:19:04 -0600 )edit

@tmonteil thank you so much for all your help! hopefully this will be my last question/problem. I am getting a syntax error for except when i enter the penultimate line (except MIPSolverException)? thank you in advance.

( 2016-12-28 10:42:47 -0600 )edit

@tmonteil ....: try:
....: p.solve() ....: if certificate: ....: bv_sol = p.get_values(bv) ....: be_sol = p.get_values(be) ....: coloration = {} ....: for v in G.vertices(): ....: for c in range(n): ....: if bv_sol[v,c] == 1: ....: coloration[v] = c ....: for e in G.edges(labels=False): ....: for c in range(n): ....: if be_sol[e,c] == 1: ....: coloration[e] = c ....: return coloration ....: else: ....: return n ....: except MIPSolverException: I then get syntax error for except

( 2017-01-03 09:04:53 -0600 )edit