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 14:44:20 +0100 )edit

( 2016-12-21 00:19:04 +0100 )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 17:42:47 +0100 )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 16:04:53 +0100 )edit

does this program mean that the decision problem of deciding whether a graph is is type I(total chromatic number=max.degree+1) or type II(total chromatic numbermax. degree +2) for those graphs which are known to satisfy the total coloring conjecture(the upper bound is the max degree+2) is polynomial time?

( 2022-07-11 19:43:41 +0100 )edit