Split permutation graphs

Korpelainen, Nicholas; Lozin, Vadim V. and Mayhill, Colin (2014). Split permutation graphs. Graphs and Combinatorics, 30(3) pp. 633–646.

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

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.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 38892
• Item Type
• Journal Item
• ISSN
• 0911-0119
• Project Funding Details

• Funded Project Name	Project ID	Funding Body
  Infinite Antichains of Combinatorial Structures	EP/J006130/1	EPSRC (Engineering and Physical Sciences Research Council)
  Not Set	EP/I01795X/1	EPSRC (Engineering and Physical Sciences Research Council)

• Keywords
• split graphs; permutation graphs, clique-width; well-quasi-order
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2013 Springer Japan
• Depositing User
• Nicholas Korpelainen