List total colorings of series-parallel graphs

DOI10.1016/j.jda.2003.12.006zbMath1105.68090OpenAlexW2171203708MaRDI QIDQ1775015

Xiao Zhou, Takao Nishizeki, Yuki Matsuo

Publication date: 4 May 2005

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2003.12.006

zbMATH Keywords

NP-completeSeries-parallel graphLinear algorithmList edge-coloringList total coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

The parameterised complexity of list problems on graphs of bounded treewidth ⋮ List total coloring of pseudo-outerplanar graphs ⋮ A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs

Cites Work

• Determining the total colouring number is NP-hard
• Planar graphs: Theory and algorithms
• Generalized coloring for tree-like graphs
• List edge and list total colourings of multigraphs
• List edge-colorings of series-parallel graphs
• Choosability, edge choosability and total choosability of outerplane graphs
• Total colourings of graphs
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: List total colorings of series-parallel graphs