Sufficient Conditions for the Existence of Perfect Heterochromatic Matchings in Colored Graphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

Sufficient Conditions for the Existence of Perfect Heterochromatic Matchings in Colored Graphs

  • Conference paper
Discrete Geometry, Combinatorics and Graph Theory (CJCDGCGT 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4381))

  • 933 Accesses

Abstract

Let G = (V, E) be an edge-colored graph. A matching of G is called heterochromatic if its any two edges have different colors. Unlike uncolored matchings for which the maximum matching problem is solvable in polynomial time, the maximum heterochromatic matching problem is NP-complete. This means that to find both sufficient and necessary good conditions for the existence of perfect heterochromatic matchings should be not easy. In this paper, we obtain sufficient conditions of Hall-type and Tutte-type for the existence of perfect heterochromatic matchings in colored bipartite graphs and general colored graphs. We also obtain a sufficient and necessary condition of Berge-type to verify if a heterochromatic matching M of G is maximum.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alon, N., Jiang, T., Miller, Z., Pritikin, D.: Properly Colored Subgraphs and Rainbow Subgraphs in Edge-Colored Graphs with Local Constraints. Random Struct. Algorithoms 23(4), 409–433 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  2. Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Macmillan, London, Elsevier, New York (1976)

    Google Scholar 

  3. Broersma, H.J., Li, X., Wöginger, G., Zhang, S.: Paths and Cycles in Colored Graphs. Australasian J. Combin. 31, 299–312 (2005)

    MATH  Google Scholar 

  4. Garey, M.R., Johnson, D.S.: Computers and Intractabilty. Freeman, New York (1979)

    Google Scholar 

  5. Jamison, R., Jiang, T., Ling, A.: Constrained Ramsey Numbers of Graphs. J. Graph Theory 42(1), 1–16 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  6. Jin, Z., Li, X.: The Complexity for Partitioning Graphs by Monochromatic Trees, Cycles and Paths. Intern. J. Computer Math. 81(11), 1357–1362 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  7. Lawler, E.L: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, Montreal Que., London (1976)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Center for Combinatorics and LPMC Nankai University, Tianjin 300071, China

    Lin Hu & Xueliang Li

Authors
  1. Lin Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xueliang Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Jin Akiyama William Y. C. Chen Mikio Kano Xueliang Li Qinglin Yu

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer Berlin Heidelberg

About this paper

Cite this paper

Hu, L., Li, X. (2007). Sufficient Conditions for the Existence of Perfect Heterochromatic Matchings in Colored Graphs. In: Akiyama, J., Chen, W.Y.C., Kano, M., Li, X., Yu, Q. (eds) Discrete Geometry, Combinatorics and Graph Theory. CJCDGCGT 2005. Lecture Notes in Computer Science, vol 4381. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70666-3_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-70666-3_6

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-70665-6

  • Online ISBN: 978-3-540-70666-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics