SpringerLink
Log in

A Min–Max Property of Chordal Bipartite Graphs with Applications

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Brandstädt, A., Hoáng, C.T.: Maximum induced matching for chordal graphs in linear time, To appear in Algorithmica

  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)

    Article  MATH  Google Scholar 

  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

  4. Cameron K.: Induced matchings. Discret. Appl. Math. 24, 97–102 (1989)

    Article  MATH  Google Scholar 

  5. Cameron K.: Induced matchings in intersection graphs. Discret. Math. 278, 1–9 (2004)

    Article  MATH  Google Scholar 

  6. Cameron K., Sritharan R., Tang Y.: Finding a maximum induced matching in weakly chordal graphs. Discret. Math. 266, 133–142 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  7. Jou-Ming C.: Induced matchings in asteroidal triple-free graphs, stability in graphs, and related topics. Discret. Appl. Math. 132, 67–78 (2004)

    Google Scholar 

  8. Cozzens M.B., Leibowitz R.: Threshold dimension of graphs. SIAM J. Algebraic Discret. Methods 5, 579–595 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  9. Dushnik B., Miller E.W.: Partially ordered sets. Am. J. Math. 63, 600–610 (1941)

    Article  MathSciNet  Google Scholar 

  10. Fricke G., Laskar R.: Strong matchings on trees. Congr. Numerantium 89, 239–243 (1992)

    MathSciNet  Google Scholar 

  11. Golumbic M.C., Laskar R.C.: Irredundancy in circular arc graphs. Discret. Appl. Math. 44, 79–89 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  12. Golumbic M.C., Lewenstein M.: New results on induced matchings. Discret. Appl. Math. 101, 157–165 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  13. Harary F., Kabell J.A., McMorris F.R.: Bipartite intersection graphs. Comm. Math. Univ. Carolinae 23, 739–745 (1982)

    MATH  MathSciNet  Google Scholar 

  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)

    Google Scholar 

  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)

  16. Hell P., Huang J.: Interval bigraphs and circular arc graphs. J. Graph Theory 46, 313–327 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  19. Müller H.: Recognizing interval digraphs and interval bigraphs in polynomial time. Dis. Appl. Math. 78, 189–205 (1997)

    Article  MATH  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  21. Trotter W.T., Bogart K.P.: On the complexity of posets. Discret. Math. 16, 71–82 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  22. West, D.B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River, NJ (1996)

  23. West D.B.: Short proofs for interval digraphs. Discret. Math. 178, 287–292 (1998)

    Article  MATH  Google Scholar 

  24. Yannakakis M.: The complexity of the partial order dimension problem. SIAM J. Algebraic Discret. Methods 10, 310–327 (1981)

    MATH  MathSciNet  Google Scholar 

  25. Yu C., Chen G., Ma T.: On the complexity of the k-chain subgraph cover problem. Theor. Comput. Sci. 205, 85–98 (1998)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, The University of Dayton, Dayton, OH, 45469-2316, USA

    Atif Abueida & Arthur H. Busch

  2. Computer Science Department, The University of Dayton, Dayton, OH, 45469, USA

    R. Sritharan

Authors
  1. Atif Abueida
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Arthur H. Busch
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. R. Sritharan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Arthur H. Busch.

Additional information

R. Sritharan is supported by a grant from the NSA.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Abueida, A., Busch, A.H. & Sritharan, R. A Min–Max Property of Chordal Bipartite Graphs with Applications. Graphs and Combinatorics 26, 301–313 (2010). https://doi.org/10.1007/s00373-010-0922-0

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-010-0922-0

Keywords

Search

Navigation