Chordal bipartite completion of colored graphs |
| |
Authors: | R Sritharan |
| |
Institution: | Computer Science Department, The University of Dayton, Dayton, OH 45469, USA |
| |
Abstract: | Golumbic, Kaplan, and Shamir Graph sandwich problems, J. Algorithms 19 (1995) 449-473], in their paper on graph sandwich problems published in 1995, left the status of the sandwich problems for strongly chordal graphs and chordal bipartite graphs open. It was recently shown C.M.H. de Figueiredo, L. Faria, S. Klein, R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoret. Comput. Sci., accepted for publication] that the sandwich problem for strongly chordal graphs is NP-complete. We show that given graph G with a proper vertex coloring c, determining whether there is a supergraph of G that is chordal bipartite and also is properly colored by c is NP-complete. This implies that the sandwich problem for chordal bipartite graphs is also NP-complete. |
| |
Keywords: | Graph Sandwich problem Chordal Chordal bipartite |
本文献已被 ScienceDirect 等数据库收录! |
|