On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs

DOI10.1016/J.JDA.2014.11.004MaRDI QIDQ2253902zbMATH OpenOpenAlexWikidataFDO

Authors Sheung-Hung Poon, Chin-Ting Ung, Yue-Li Wang, Ton Kloks

Publication date 13 February 2015

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

Full work available at URL https://arxiv.org/abs/1110.3583

zbMATH Keywords

induced matchingstrong chromatic indexpermutation graphchordal bipartite graphtree-cograph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We show that there exist linear-time algorithms that compute the strong chromatic index and a maximum induced matching of tree-cographs when the decomposition tree is a part of the input. We also show that there exist efficient algorithms for the strong chromatic index of (bipartite) permutation graphs and of chordal bipartite graphs.

Recommendations

• The strong chromatic index of a class of graphs
• A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
• Strong edge-colouring and induced matchings
• Publication:3201075
• Strong chromatic index of chordless graphs

Cites work

• scientific article; zbMATH DE number 434499 (Why is no real title available?)
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3851125 (Why is no real title available?)
• scientific article; zbMATH DE number 3851153 (Why is no real title available?)
• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• A Characterization of Block-Graphs
• A characterization of ptolemaic graphs
• A characterization of totally balanced hypergraphs
• A min-max property of chordal bipartite graphs with applications
• A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• Bipartite permutation graphs
• Characterizations of derived graphs
• Characterizations of strongly chordal graphs
• Characterizations of totally balanced matrices
• Computing the Minimum Fill-In is NP-Complete
• Difference graphs
• Finding a maximum induced matching in weakly chordal graphs
• Hypergraphs with no special cycles
• Improved algorithms for weakly chordal graphs
• Induced matchings
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Maximum induced matchings for chordal graphs in linear time
• NP-completeness of some generalizations of the maximum matching problem
• On rigid circuit graphs
• On the computational complexity of strong edge coloring
• Perfect Elimination and Chordal Bipartite Graphs
• Representation characterizations of chordal bipartite graphs
• Representation of a finite graph by a set of intervals on the real line
• Strong tree-cographs are Birkhoff graphs
• The strong perfect graph theorem
• Three Partition Refinement Algorithms
• Trapezoid graphs and generalizations, geometry and algorithms
• Trapezoid graphs and their coloring
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Treewidth. Computations and approximations
• Weakly triangulated graphs

Cited in

(3)

• scientific article; zbMATH DE number 434499 (Why is no real title available?)
• On strictly chordality-\(k\) graphs
• A polynomial time algorithm for strong edge coloring of partial \(k\)-trees

This page was built for publication: On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2253902)