Skip to main content
Article
Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone
Journal of Combinatorial Optimization
  • Pinar Heggernes, University of Bergen
  • Federico Mancini, University of Bergen
  • Charis Papadopoulos, University of Ioannina
  • R. Sritharan, University of Dayton
Document Type
Article
Publication Date
10-1-2011
Abstract

A graph class is sandwich monotone if, for every pair of its graphs G1=(V,E1) and G2=(V,E2) with E1⊂E2, there is an ordering e1,…,ek of the edges in E2∖E1 such that G=(V,E1∪{e1,…,ei }) belongs to the class for every i between 1 and k. In this paper we show that strongly chordal graphs and chordal bipartite graphs are sandwich monotone, answering an open question by Bakonyi and Bono (Czechoslov. Math. J. 46:577–583, 1997). So far, very few classes have been proved to be sandwich monotone, and the most famous of these are chordal graphs. Sandwich monotonicity of a graph class implies that minimal completions of arbitrary graphs into that class can be recognized and computed in polynomial time. For minimal completions into strongly chordal or chordal bipartite graphs no polynomial-time algorithm has been known. With our results such algorithms follow for both classes. In addition, from our results it follows that all strongly chordal graphs and all chordal bipartite graphs with edge constraints can be listed efficiently.

Inclusive pages
438–456
ISBN/ISSN
1382-6905
Comments

Permission documentation on file.

Publisher
Springer
Peer Reviewed
Yes
Citation Information
Pinar Heggernes, Federico Mancini, Charis Papadopoulos and R. Sritharan. "Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone" Journal of Combinatorial Optimization Vol. 22 Iss. 3 (2011)
Available at: http://works.bepress.com/r_sritharan/8/