A Polynomial-Time Algorithm for Finding Total Colorings of Partial k-Trees
Copyright policy )A Polynomial-Time Algorithm for Finding Total Colorings of Partial k-Trees
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. Many combinatorial problems can be efficiently solved for partial k-trees, that is, graphs of treewidth bounded by a constant k. However, no polynomial-time algorithm has been known for the problem of finding a total coloring of a given partial k-tree with the minimum number of colors. This paper gives such a first polynomial-time algorithm.
- Tohoku University Japan
quad-count, partial \(k\)-tree, Trees, Coloring of graphs and hypergraphs, total coloring, Graph algorithms (graph-theoretic aspects), Analysis of algorithms, pair-count
quad-count, partial \(k\)-tree, Trees, Coloring of graphs and hypergraphs, total coloring, Graph algorithms (graph-theoretic aspects), Analysis of algorithms, pair-count
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).7 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!