A counterexample regarding labelled well-quasi-ordering. (English) Zbl 1402.05182
Summary: N. Korpelainen et al. [Order 30, No. 3, 723–735 (2013; Zbl 1276.05062)] conjectured that a hereditary property of graphs which is well-quasi-ordered by the induced subgraph order and defined by only finitely many minimal forbidden induced subgraphs is labelled well-quasi-ordered, a notion stronger than that of \(n\)-well-quasi-order introduced by M. Pouzet [C. R. Acad. Sci., Paris, Sér. A 274, 1677–1680 (1972; Zbl 0254.08001)]. We present a counterexample to this conjecture. In fact, we exhibit a hereditary property of graphs which is well-quasi-ordered by the induced subgraph order and defined by finitely many minimal forbidden induced subgraphs yet is not 2-well-quasi-ordered. This counterexample is based on the widdershins spiral, which has received some study in the area of permutation patterns.
MSC:
| 05C78 | Graph labelling (graceful graphs, bandwidth, etc.) |
References:
| [1] | Atkinson, M.D.: Restricted permutations. Discret. Math. 195(1-3), 27-38 (1999) · Zbl 0932.05002 · doi:10.1016/S0012-365X(98)00162-9 |
| [2] | Atminas, A., Brignall, R., Lozin, V., Stacho, J.: Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs. arXiv:1503.01628 [math.CO] · Zbl 1460.05161 |
| [3] | Atminas, A., Lozin, V.: Labelled induced subgraphs and well-quasi-ordering. Order 32(3), 313-328 (2015) · Zbl 1325.05141 · doi:10.1007/s11083-014-9333-9 |
| [4] | Avis, D.M., Newborn, M.: On pop-stacks in series. Utilitas Math. 19, 129-140 (1981) · Zbl 0461.68060 |
| [5] | Benzaken, C., Hammer, P.L., de Werra, D.: Split graphs of Dilworth number \[22\]. Discret. Math. 55(2), 123-127 (1985) · Zbl 0573.05047 · doi:10.1016/0012-365X(85)90040-8 |
| [6] | Bose, P., Buss, J.F., Lubiw, A.: Pattern matching for permutations. Inform. Process. Lett. 65(5), 277-283 (1998) · Zbl 1338.68304 · doi:10.1016/S0020-0190(97)00209-3 |
| [7] | Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999) · Zbl 0919.05001 · doi:10.1137/1.9780898719796 |
| [8] | Brignall, R., Huczynska, S., Vatter, V.R.: Decomposing simple permutations, with enumerative consequences. Combinatorica 28(4), 385-400 (2008) · Zbl 1164.05001 · doi:10.1007/s00493-008-2314-0 |
| [9] | Daligault, J., Rao, M., Thomassé, S.: Well-quasi-order of relabel functions. Order 27(3), 301-315 (2010) · Zbl 1209.05210 · doi:10.1007/s11083-010-9174-0 |
| [10] | Damaschke, P.: Induced subgraphs and well-quasi-ordering. J. Graph Theory 14(4), 427-435 (1990) · Zbl 0721.05059 · doi:10.1002/jgt.3190140406 |
| [11] | Dushnik, B., Miller, E.W.: Partially ordered sets. Am. J. Math. 63, 600-610 (1941) · JFM 67.0157.01 · doi:10.2307/2371374 |
| [12] | Földes, S., Hammer, P.L.: Split graphs. Congr. Numer. 14, 311-315 (1977) · Zbl 0407.05071 |
| [13] | Földes, S., Hammer, P.L.: Split graphs having Dilworth number two. Can. J. Math. 29(3), 666-672 (1977) · Zbl 0335.05130 · doi:10.4153/CJM-1977-069-1 |
| [14] | Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar. 18, 25-66 (1967) · Zbl 0153.26002 · doi:10.1007/BF02020961 |
| [15] | Higman, G.: Ordering by divisibility in abstract algebras. Proc. Lond. Math. Soc. 3(2), 326-336 (1952) · Zbl 0047.03402 · doi:10.1112/plms/s3-2.1.326 |
| [16] | Homberger, C., Pantone, J.: PermPy. http://permpy.com/ (2017) |
| [17] | Huczynska, S., Ruškuc, N.: Well quasi-order in combinatorics: embeddings and homomorphisms. In: Czumaj, A., Georgakopoulos, A., Král’, D., Lozin, V., Pikhurko, O. (eds.) Surveys in Combinatorics 2015, vol. 424 of London Mathematical Society Lecture Note Series, pp. 261-293. Cambridge University Press, Cambridge (2015) · Zbl 1352.05008 |
| [18] | Information System on Graph Classes and their Inclusions (ISGCI). Published electronically at http://www.graphclasses.org/ |
| [19] | Korpelainen, N., Lozin, V., Mayhill, C.: Split permutation graphs. Graphs Combin. 30(3), 633-646 (2014) · Zbl 1294.05132 · doi:10.1007/s00373-013-1290-3 |
| [20] | Korpelainen, N., Lozin, V., Razgon, I.: Boundary properties of well-quasi-ordered sets of graphs. Order 30(3), 723-735 (2013) · Zbl 1276.05062 · doi:10.1007/s11083-012-9272-2 |
| [21] | Murphy, M.M.: Restricted Permutations, Antichains, Atomic Classes, and Stack Sorting. PhD thesis, University of St Andrews (2002). http://hdl.handle.net/10023/11023 |
| [22] | Pouzet, M.: Un bel ordre d’abritement et ses rapports avec les bornes d’une multirelation. C. R. Acad. Sci. Paris Sér. A-B 274, A1677-A1680 (1972) · Zbl 0254.08001 |
| [23] | Robertson, N., Seymour, P.: Graph minors I-XX. J. Combin. Theory Ser. B (1983-2004) · Zbl 0521.05062 |
| [24] | Stankova, Z.E.: Forbidden subsequences. Discret. Math. 132(1-3), 291-316 (1994) · Zbl 0810.05011 · doi:10.1016/0012-365X(94)90242-9 |
| [25] | Vatter, VR; Bóna, M. (ed.), Permutation classes, 754-833 (2015), Boca Raton · Zbl 1353.05010 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
