TY - GEN

T1 - A linear algorithm for finding total colorings of partial fc-trees

AU - Isobe, Shuji

AU - Zhou, Xiao

AU - Nishizeki, Takao

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.

PY - 1999

Y1 - 1999

N2 - A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, in such a way that no two adjacent or incident elements receive the same color. The total coloring problem is to find a total coloring of a given graph with the minimum number of colors. Many combinatorial problems can be efficiently solved for partial k-trees, i.e., graphs with bounded tree-width. However, no efficient algorithm has been known for the total coloring problem on partial fc-trees although a polynomial-time algorithm of very high order has been known. In this paper, we give a linear-time algorithm for the total coloring problem on partial fc-trees with bounded fc.

AB - A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, in such a way that no two adjacent or incident elements receive the same color. The total coloring problem is to find a total coloring of a given graph with the minimum number of colors. Many combinatorial problems can be efficiently solved for partial k-trees, i.e., graphs with bounded tree-width. However, no efficient algorithm has been known for the total coloring problem on partial fc-trees although a polynomial-time algorithm of very high order has been known. In this paper, we give a linear-time algorithm for the total coloring problem on partial fc-trees with bounded fc.

UR - http://www.scopus.com/inward/record.url?scp=33746049102&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33746049102&partnerID=8YFLogxK

U2 - 10.1007/3-540-46632-0_35

DO - 10.1007/3-540-46632-0_35

M3 - Conference contribution

AN - SCOPUS:33746049102

SN - 3540669167

SN - 9783540669166

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 347

EP - 356

BT - Algorithms and Computation - 10th International Symposium, ISAAC 1999, Proceedings

A2 - Rangan, C. Pandu

A2 - Aggarwal, Alok

PB - Springer Verlag

T2 - 10th Annual International Symposium on Algorithms and Computation, ISAAC 1999

Y2 - 16 December 1999 through 18 December 1999

ER -