Skip to main content
SpringerLink
Log in

Split Permutation Graphs

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

Abstract

The class of split permutation graphs is the intersection of two important classes, the split graphs and permutation graphs. It also contains an important subclass, the threshold graphs. The class of threshold graphs enjoys many nice properties. In particular, these graphs have bounded clique-width and they are well-quasi-ordered by the induced subgraph relation. It is known that neither of these two properties is extendable to split graphs or to permutation graphs. In the present paper, we study the question of extendability of these two properties to split permutation graphs. We answer this question negatively with respect to both properties. Moreover, we conjecture that with respect to both of them the split permutation graphs constitute a critical 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. Benzaken C., Hammer P.L., de Werra D.: Split graphs of Dilworth number 2. Discret. Math. 55, 123–127 (1985)

    Article  MATH  Google Scholar 

  2. Brandstädt A., Lozin V.: On the linear structure and clique-width of bipartite permutation graphs. Ars Combinatoria 67, 273–281 (2003)

    MATH  MathSciNet  Google Scholar 

  3. Chvátal V., Hammer P.L.: Aggregation of inequalities in integer programming. Ann. Discret Math. 1, 145–162 (1977)

    Article  Google Scholar 

  4. Courcelle B.: Clique-width of countable graphs: a compactness property. Discret. Math. 276, 127–148 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  5. Courcelle B., Engelfriet J., Rozenberg G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46, 218–270 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  6. Daligault J., Rao M., Thomassé S.: Well-quasi-order of relabel functions. Order 27, 301–315 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  7. Damaschke P.: Induced subgraphs and well-quasi-ordering. J. Graph Theory 14, 427–435 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  8. Ding G.: Subgraphs and well-quasi-ordering. J. Graph Theory 16, 489–502 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  9. Ding G.: On canonical antichains. Discret. Math. 309, 1123–1134 (2009)

    Article  MATH  Google Scholar 

  10. Földes S., Hammer P.L.: Split graphs. Congr. Numer. 19, 311–315 (1977)

    Google Scholar 

  11. Golumbic M.C., Rotics U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11, 423–443 (2000)

    Article  MathSciNet  Google Scholar 

  12. Kaminski M., Lozin V.V., Milanič M.: Recent developments on graphs of bounded clique-width. Discret. Appl. Math. 157, 2747–2761 (2009)

    Article  MATH  Google Scholar 

  13. Lozin V.V.: Minimal classes of graphs of unbounded clique width. Ann. Comb. 15, 707–722 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  14. Lozin V.V., Mayhill C.: Canonical antichains of unit interval and bipartite permutation graphs. Order 28, 513–522 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  15. Makowsky J.A., Rotics U.: On the clique-width of graphs with few P 4’s. Int. J. Found. Comput. Sci. 10, 329–348 (1999)

    Article  MathSciNet  Google Scholar 

  16. Petkovšek M.: Letter graphs and well-quasi-order by induced subgraphs. Discret. Math. 244, 375–388 (2002)

    Article  MATH  Google Scholar 

  17. Robertson N., Seymour P.D.: Graph minors. XX. Wagner’s conjecture. J. Comb. Theory Ser. B 92, 325–357 (2004)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, The Open University, Milton Keynes, UK

    Nicholas Korpelainen

  2. DIMAP, Mathematics Institute, University of Warwick, Coventry, CV4 7AL, UK

    Vadim V. Lozin & Colin Mayhill

Authors
  1. Nicholas Korpelainen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vadim V. Lozin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Colin Mayhill
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vadim V. Lozin.

Additional information

Nicholas Korpelainen: Research of this author was partially supported by EPSRC grant EP/J006130/1.Vadim V. Lozin: The author gratefully acknowledges support from DIMAP—the Center for Discrete Mathematics and its Applications at the University of Warwick, and from EPSRC, grant EP/I01795X/1.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Korpelainen, N., Lozin, V.V. & Mayhill, C. Split Permutation Graphs. Graphs and Combinatorics 30, 633–646 (2014). https://doi.org/10.1007/s00373-013-1290-3

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-013-1290-3

Keywords

Search

Navigation