Skip to main content
SpringerLink
Log in

On the vertex packing problem

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

Abstract

A forbidden subgraphs characterization of the class of graphs that arise from bipartite graphs, odd holes, and graphs with no complement of a diamond via repeated substitutions is given. This characterization allows us to solve the vertex packing problem for the graphs in this class.

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

Access this article

Log in via an institution

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. Berge, C.: Graphs, and Hypergraphs, Amsterdam: North-Holland 1973

    Google Scholar 

  2. Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications London: Macmillian 1976

    Google Scholar 

  3. Chvátal, V., Sbihi, N.: Bull-Free Graphs Are Perfect, Graphs and Combinatorics3, 127–139 (1987)

    Google Scholar 

  4. De Simone, C., Sassano, A.: Stability Number of Bull and Chair Free Graphs, IASI Technical Report R. 258, May 1989 (to appear in Discrete Applied Mathematics)

  5. Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems, Theor. Comput. Sci.1, 237–267 (1976)

    Google Scholar 

  6. Grötschel, M., Lovász, L., and Schrijver, A.: Polynomial Algorithms for Perfect Graphs, in: C. Berge and V. Chvátel, eds., Topics on Perfect Graphs (Annals of Discrete Mathematics21, pp. 325–356) 1984

  7. Hammer, P.L., Mahadev, N.V.R., De, Werra, D.: The Struction Of A Graph: Application To CN-free Graphs, Combinatorica5, 141–147 (1985)

    Google Scholar 

  8. Hsu, W.-L., Ikura, Y., Nemhauser, G.L.: A polynomial Algorithm For Maximum Weighted Vertex Packing On Graphs Without Long Odd Cycles, Math. Programming20, 225–232 (1982)

    Google Scholar 

  9. Lovász, L., Plummer, M.D.: Matching theory. Annals of Discrete Mathematics29, (1986)

  10. Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. of Comb. Theory Ser.B28, 284–304 (1980)

    Google Scholar 

  11. Poljak, S.: A note on stable sets and coloring of graphs, Comment. Math. Univ. Carrolin15, 307–309 (1974)

    Google Scholar 

  12. Sbihi, N.: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile, Discrete Math.29, 53–76 (1980)

    Google Scholar 

  13. Seinsche, D.: On a property of the class ofn-colourable graphs. J. Comb. Theory Ser.B16, 191–193 (1974)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Istituto di Analisi dei Sistemi ed Informatica del CNR, Viale Manzoni 30, 00185, Roma, Italy

    C. De Simone

Authors
  1. C. De Simone
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

De Simone, C. On the vertex packing problem. Graphs and Combinatorics 9, 19–30 (1993). https://doi.org/10.1007/BF01195324

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01195324

Keywords

Search

Navigation