[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Clique-Perfectness of Claw-Free Planar Graphs

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

Abstract

A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. An open problem concerning clique-perfect graphs is to find all minimal forbidden induced subgraphs of clique-perfect graphs. In this paper we characterize the clique-perfectness of claw-free planar graphs by forbidden induced subgraphs. Furthermore, we also characterize the clique-perfectness of claw-free graphs with degree at most 4 and graphs with degree at most 3. As an immediate corollary, we show that claw-free cubic graphs are clique-perfect.

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
$34.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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Balachandran, V., Nagavamsi, P., Rangan, C.P.: Clique transversal and clique independence on comparability graphs. Inform. Process. Lett. 58, 181–184 (1996)

    Article  MathSciNet  Google Scholar 

  2. Bondy J.A., Murty, U.S.R.: Graph Theory. Springer, New York (2008)

  3. Bonomo, F., Chudnovsky, M., Durán, G.: Partial characterizations of clique-perfect graphs I: subclasses of claw-free graphs. Discrete Appl. Math. 156, 1058–1082 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bonomo, F., Chudnovsky, M., Durán, G.: Partial characterizations of clique-perfect graphs II: diamond-free and Helly circular-arc graphs. Discrete Math. 309, 3485–3499 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bonomo, F., Durán, G., Groshaus, M., Szwarcfiter, J.L.: On clique-perfect and K-perfect graphs. Ars Combin. 80, 97–112 (2006)

    MathSciNet  MATH  Google Scholar 

  6. Bonomo, F., Durán, G., Lin, M.C., Szwarcfiter, J.L.: On balanced graphs. Math. Program. Ser. B 105, 233–250 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K.: Clique-perfectness of complements of line graphs. Discrete Appl. Math. 186, 19–44 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bonomo, F., Durán, G., Soulignac, F., Sueiro, G.: Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs. Discrete Appl. Math. 157, 3511–3518 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  9. Brandstädt, A., Chepoi, V.D., Dragan, F.F.: Clique \(r\)-domination and clique \(r\)-packing problems on dually chordal graphs. SIAM J. Discrete Math. 10, 109–127 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  10. Chang, G.J., Farber, M., Tuza, Z.S.: Algorithmic aspects of neighbourhood numbers. SIAM J. Discrete Math. 6, 24–29 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  11. Chudnovsky, M., Roberston, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51–229 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  12. Dahlhaus, E., Mannuel, P.D., Miller, M.: Maximum \(h\)-colourable subgraph problem in balanced graphs. Inform. Process. Lett. 65, 301–303 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  13. Durán, G., Lin, M.C., Szwarcfiter, J.L.: On clique-transversals and clique-independent sets. Ann. Oper. Res. 116, 71–77 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  14. Golumbic, M.: Algorithmic graph theory and perfect graphs. Academic, New York (1980)

    MATH  Google Scholar 

  15. Guruswami, V., Rangan, C.P.: Algorithmic aspects of clique-transversal and clique-independent sets. Discrete Appl. Math. 100, 183–202 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  16. Lee, C.M., Chang, M.S.: Distance-hereditary graphs are clique-perfect. Discrete Appl. Math. 154, 525–536 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  17. Plummer, M.D.: Extending matchings in claw-free graphs. Discrete Math. 125, 301–307 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  18. Prisner, E.: Hereditary clique-Helly graphs. J. Combin. Math. Combin. Comput. 14, 216–220 (1993)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Management, Qufu Normal University, Rizhao, 276800, China

    Zuosong Liang

  2. School of Management, Shanghai University, Shanghai, 200444, China

    Erfang Shan

  3. Mathematics Department, Shanghai University, Shanghai, 200444, China

    Liying Kang

Authors
  1. Zuosong Liang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Erfang Shan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Liying Kang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Erfang Shan.

Additional information

This research was partially supported by the National Nature Science Foundation of China (Nos. 11571222 and 11471210), the Postdoctoral Foundation of China (No. 2016M592156) and the Nature Science Foundation of Shandong Province, China (No. ZR2014AQ008).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liang, Z., Shan, E. & Kang, L. Clique-Perfectness of Claw-Free Planar Graphs. Graphs and Combinatorics 32, 2551–2562 (2016). https://doi.org/10.1007/s00373-016-1726-7

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-016-1726-7

Keywords

Mathematics Subject Classification