A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES

DOI10.1142/S0129054199000137zbMath1320.05123OpenAlexW2043098473MaRDI QIDQ5248998

Xiao Zhou, Shuji Isobe, Takao Nishizeki

Publication date: 29 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054199000137

zbMATH Keywords

partial \(k\)-treetotal coloringpair-countquad-count

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ The minimum vulnerability problem on specific graph classes ⋮ The Minimum Vulnerability Problem on Graphs

Cites Work

• Determining the total colouring number is NP-hard
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Easy problems for tree-decomposable graphs
• Edge-Coloring Partialk-Trees
• Linear-time computability of combinatorial problems on series-parallel graphs
• An algebraic theory of graph reduction
• An NC Parallel Algorithm for Edge-Coloring Series–Parallel Multigraphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• A Linear Algorithm for Edge-Coloring Series–Parallel Multigraphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES