Algorithms for the strong chromatic index of Halin graphs, distance-hereditary graphs and maximal outerplanar graphs

2011/10/04 by Ton Kloks, Sheung-Hung Poon, Kloks, Ton +5
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1110.0583

arxiv created 2011/10/04 · arxiv updated 2011/10/05

Abstract

We show that there exist linear-time algorithms that compute the strong chromatic index of Halin graphs, of maximal outerplanar graphs and of distance-hereditary graphs.

Related

• A linear-time algorithm for the strong chromatic index of Halin graphs
• On the strong chromatic index and induced matching of tree-cographs, permutation graphs and chordal bipartite graphs
• On the strong chromatic index and maximum induced matching of tree-cographs and permutation graphs
• The Strong Chromatic Index of graphs with maximum degree Δ
• Further results on strong edge-colourings in outerplanar graphs