A polynomial time algorithm for strong edge coloring of partial \(k\)-trees

DOI10.1016/j.dam.2004.03.001zbMath1062.68091OpenAlexW2083057776MaRDI QIDQ1887062

Mohammad R. Salavatipour

Publication date: 23 November 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.03.001

zbMATH Keywords

Edge coloringStrong matchingBounded tree-widthStrong edge coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

Strong edge-coloring for cubic Halin graphs ⋮ Strong edge chromatic index of the generalized Petersen graphs ⋮ The strong chromatic index of Halin graphs ⋮ On the strong chromatic index of cubic Halin graphs ⋮ Strong edge-colouring and induced matchings ⋮ Algorithms for finding distance-edge-colorings of graphs ⋮ On the complexity of the flow coloring problem ⋮ Generalizing the induced matching by edge capacity constraints ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ On the approximability of the maximum induced matching problem ⋮ Strong edge-coloring for jellyfish graphs ⋮ Proof of a conjecture on the strong chromatic index of Halin graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Irredundancy in circular arc graphs
• Induced matchings in bipartite graphs
• Graph minors. V. Excluding a planar graph
• NP-completeness of some generalizations of the maximum matching problem
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Induced matchings
• On the computational complexity of strong edge coloring
• New results on induced matchings
• Graph minors. IV: Tree-width and well-quasi-ordering
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Edge-Coloring Partialk-Trees
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Optimal approximation of sparse hessians and its equivalence to a graph coloring problem
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: A polynomial time algorithm for strong edge coloring of partial \(k\)-trees