New Results on Chordal-\((k, 1)\) and Strongly Chordal-\((k, 1)\) Sandwich Problems

The chordal-(\(k,l\)) sandwich and strongly chordal-(\(k,l\)) sandwich problems were considered in recent work [8, 9] where classification of the complexities of the problems for all possible nonnegative integer values for \(k, l\) was considered. We extend the classification in [8, 9] by presenting polynomial time algorithms for some cases that remained open; currently, very few graph sandwich problems are known to be solvable in polynomial time.