A min-max property of chordal bipartite graphs with applications. (English) Zbl 1219.05136
Summary: We show that if \(G\) is a bipartite graph with no induced cycles on exactly 6 vertices, then the minimum number of chain subgraphs of \(G\) needed to cover \(E(G)\) equals the chromatic number of the complement of the square of line graph of \(G\). Using this, we establish that for a chordal bipartite graph \(G\), the minimum number of chain subgraphs of \(G\) needed to cover \(E(G)\) equals the size of a largest induced matching in \(G\), and also that a minimum chain subgraph cover can be computed in polynomial time. The problems of computing a minimum chain cover and a largest induced matching are NP-hard for general bipartite graphs. Finally, we show that our results can be used to efficiently compute a minimum chain subgraph cover when the input is an interval bigraph.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Brandstädt, A., Hoáng, C.T.: Maximum induced matching for chordal graphs in linear time, To appear in Algorithmica · Zbl 1171.68595 |
| [2] | Brandstädt A., Eschen E.M., Sritharan R.: The induced matching and chain subgraph cover problems for convex bipartite graphs. Theor. Comput. Sci. 381, 260–265 (2007) · Zbl 1188.68209 · doi:10.1016/j.tcs.2007.04.006 |
| [3] | Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. In: SIAM monographs on discrete mathematics and applications. Society for Industrial and Applied Mathematics, Philadelphia, 1999 · Zbl 0919.05001 |
| [4] | Cameron K.: Induced matchings. Discret. Appl. Math. 24, 97–102 (1989) · Zbl 0687.05033 · doi:10.1016/0166-218X(92)90275-F |
| [5] | Cameron K.: Induced matchings in intersection graphs. Discret. Math. 278, 1–9 (2004) · Zbl 1033.05080 · doi:10.1016/j.disc.2003.05.001 |
| [6] | Cameron K., Sritharan R., Tang Y.: Finding a maximum induced matching in weakly chordal graphs. Discret. Math. 266, 133–142 (2003) · Zbl 1022.05064 · doi:10.1016/S0012-365X(02)00803-8 |
| [7] | Jou-Ming C.: Induced matchings in asteroidal triple-free graphs, stability in graphs, and related topics. Discret. Appl. Math. 132, 67–78 (2004) · Zbl 1029.05120 |
| [8] | Cozzens M.B., Leibowitz R.: Threshold dimension of graphs. SIAM J. Algebraic Discret. Methods 5, 579–595 (1984) · Zbl 0717.05069 · doi:10.1137/0605055 |
| [9] | Dushnik B., Miller E.W.: Partially ordered sets. Am. J. Math. 63, 600–610 (1941) · Zbl 0025.31002 · doi:10.2307/2371374 |
| [10] | Fricke G., Laskar R.: Strong matchings on trees. Congr. Numerantium 89, 239–243 (1992) · Zbl 0786.05065 |
| [11] | Golumbic M.C., Laskar R.C.: Irredundancy in circular arc graphs. Discret. Appl. Math. 44, 79–89 (1993) · Zbl 0783.05059 · doi:10.1016/0166-218X(93)90223-B |
| [12] | Golumbic M.C., Lewenstein M.: New results on induced matchings. Discret. Appl. Math. 101, 157–165 (2000) · Zbl 0951.68104 · doi:10.1016/S0166-218X(99)00194-8 |
| [13] | Harary F., Kabell J.A., McMorris F.R.: Bipartite intersection graphs. Comm. Math. Univ. Carolinae 23, 739–745 (1982) · Zbl 0516.05049 |
| [14] | Hayward, R.B., Hoàng, C.T., Maffray, F.: Optimizing weakly triangulated graphs, Graphs Combinatorics 5, 339–349 (1989); erratum in 6, 33–35 (1990) · Zbl 0679.68082 |
| [15] | Hayward, R.B., Spinrad, J.P., Sritharan, R.: Weakly chordal graph algorithms via handles. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 42–49 (2000) · Zbl 0956.68104 |
| [16] | Hell P., Huang J.: Interval bigraphs and circular arc graphs. J. Graph Theory 46, 313–327 (2004) · Zbl 1046.05066 · doi:10.1002/jgt.20006 |
| [17] | Kimble, R.: Extremal problems in dimension theory for partially ordered sets, Ph. D. thesis, Massachusetts Institute of Technology, Cambridge (1973) |
| [18] | Ma T., Spinrad J.P.: On the 2-chain subgraph cover and related problems. J. Algorithms 17, 251–268 (1994) · Zbl 0821.68097 · doi:10.1006/jagm.1994.1034 |
| [19] | Müller H.: Recognizing interval digraphs and interval bigraphs in polynomial time. Dis. Appl. Math. 78, 189–205 (1997) · Zbl 0890.68103 · doi:10.1016/S0166-218X(97)00027-9 |
| [20] | Sen M., Das S., Roy A.B., West D.B.: Interval digraphs: an analogue of interval graphs. J. Graph Theory 13, 581–592 (1989) · Zbl 0689.05025 · doi:10.1002/jgt.3190130508 |
| [21] | Trotter W.T., Bogart K.P.: On the complexity of posets. Discret. Math. 16, 71–82 (1976) · Zbl 0351.06003 · doi:10.1016/0012-365X(76)90095-9 |
| [22] | West, D.B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River, NJ (1996) · Zbl 0845.05001 |
| [23] | West D.B.: Short proofs for interval digraphs. Discret. Math. 178, 287–292 (1998) · Zbl 0884.05044 · doi:10.1016/S0012-365X(97)81840-7 |
| [24] | Yannakakis M.: The complexity of the partial order dimension problem. SIAM J. Algebraic Discret. Methods 10, 310–327 (1981) |
| [25] | Yu C., Chen G., Ma T.: On the complexity of the k-chain subgraph cover problem. Theor. Comput. Sci. 205, 85–98 (1998) · Zbl 0913.68004 · doi:10.1016/S0304-3975(97)00036-4 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
