Total-chromatic number and chromatic index of dually chordal graphs

Given a graph G and a vertex nu, a vertex u is an element of N(nu) is a maximum neighbor of nu if for all w is an element of N(nu) we have N(zu) subset of or equal to N(u), where N(nu) denotes the neighborhood of nu in G. A maximum neighborhood elimination order of G is a linear order nu(1), nu(2),..., nu(n) on its vertex set such that there is a maximum neighbor of v(i) in the subgraph G[v(1),..., v(i)]. A graph is dually chordal if it admits a maximum neighborhood elimination order. Alternatively, a graph is dually chordal if it is the clique graph of a chordal graph. The class of dually chordal graphs generalizes known subclasses of chordal graphs such as doubly chordal graphs, strongly chordal graphs, interval graphs, and indifference graphs. We prove that Vizing's total-color conjecture holds for dually chordal graphs. We describe a new heuristic that Fields an exact total coloring for even maximum degree dually chordal graphs and an exact edge coloring for odd maximum degree dually chordal graphs. (C) 1999 Elsevier Science B.V. All rights reserved.