Intersection of chordal graphs and some related partition problems

DOI10.1016/J.DAM.2024.10.010MaRDI QIDQ6657232zbMATH OpenFDO

Authors Atif A. Abueida, Arthur H. Busch, R. Sritharan

Publication date 6 January 2025

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

Full work available at URL https://doi.org/10.1016/J.DAM.2024.10.010

zbMATH Keywords

chordal graphchordalityintersection of graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• LATIN 2004: Theoretical Informatics
• Join colourings of chordal graphs
• scientific article; zbMATH DE number 617574
• Partitioning chordal graphs
• Partitioning chordal graphs into independent sets and cliques

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A special planar satisfiability problem and a consequence of its NP- completeness
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Induced matchings
• Intersection dimensions of graph classes
• New bounds for matrix multiplication: from alpha to omega
• New min-max theorems for weakly chordal and dually chordal graphs
• On dimensional properties of graphs
• On the 2-Chain Subgraph Cover and Related Problems
• On the chordality of a graph
• On the computational complexity of (O,P)-partition problems
• Partitions of graphs into one or two independent sets and cliques
• The complexity of some problems related to GRAPH 3-COLORABILITY
• The Complexity of the Partial Order Dimension Problem

Cited in

(1)

• Graphs of bounded chordality

This page was built for publication: Intersection of chordal graphs and some related partition problems

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