{"entities":{"Q1953423":{"pageid":1964165,"ns":120,"title":"Item:Q1953423","lastrevid":57629724,"modified":"2026-03-31T16:43:29Z","type":"item","id":"Q1953423","labels":{"en":{"language":"en","value":"Multiple Petersen subdivisions in permutation graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6171876"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953423$D916EC62-1A9F-43C3-8ED7-B897A0F474E4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5d32436e1d09cb11d46e519549b49085bd12b9c5","datavalue":{"value":{"text":"Multiple Petersen subdivisions in permutation graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1953423$162E4052-4159-4390-A197-304C1A3C8696","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3c6b99ba8cfdeff1fb79fbb740681f4ff4f00331","datavalue":{"value":"1266.05172","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953423$E31ED6B2-3A56-4432-B15C-A6C78A93EEA2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8df0ebc0c42f35d05a59dce509c57e3cf22f3034","datavalue":{"value":{"entity-type":"item","numeric-id":322208,"id":"Q322208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953423$7E353C92-A09F-4847-A66D-018DCF5431D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c48a7603bb176194a4d769e86fb77a38db85a82","datavalue":{"value":{"entity-type":"item","numeric-id":344456,"id":"Q344456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953423$0500E309-0FCC-488D-BA9B-2056E8A17FAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ce416b700b8eabc571e89ef206830201d09a568","datavalue":{"value":{"entity-type":"item","numeric-id":409379,"id":"Q409379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953423$57D7D3D9-0746-4293-A5FF-E296114DCF8C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953423$40B75025-6D0B-4D09-9E00-F07A12645492","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4a8303ee696998ba030c9b1c3b6bc07c6038c334","datavalue":{"value":{"time":"+2013-06-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1953423$FD20FD7F-0C3F-4E51-881A-9930582C9C53","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2c67ff21b9eb0cb58689d88ff86f43adb4241a65","datavalue":{"value":"https://arxiv.org/abs/1204.1989","type":"string"},"datatype":"url"},"type":"statement","id":"Q1953423$BBF523D9-01A2-4D22-A35A-8309EBDFDD39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"d594350ef50e8440074d1448770246e8ddaf427a","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p37","type":"string"},"datatype":"url"},"type":"statement","id":"Q1953423$FCFC5755-F24C-4218-A2E4-2FB442E2C391","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0fe07c022e0b36eaf11c48656ccebdfa98705290","datavalue":{"value":"Summary: A permutation graph is a cubic graph admitting a 1-factor \\(M\\) whose complement consists of two chordless cycles. Extending results of \\textit{M. N. Ellingham} [Congr. Numerantium 44, 33--40 (1984; Zbl 0558.05040)] and of \\textit{J. L. Goldwasser} and \\textit{C.-Q. Zhang} [Ars Comb. 51, 240--248 (1999; Zbl 0977.05067)], we prove that if \\(e\\) is an edge of \\(M\\) such that every 4-cycle containing an edge of \\(M\\) contains \\(e\\), then \\(e\\) is contained in a subdivision of the Petersen graph of a special type.    In particular, if the graph is cyclically 5-edge-connected, then every edge of \\(M\\) is contained in such a subdivision. Our proof is based on a characterization of cographs in terms of twin vertices. We infer a linear lower bound on the number of Petersen subdivisions in a permutation graph with no 4-cycles, and give a construction showing that this lower bound is tight up to a constant factor.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953423$53159032-2A3E-422F-AA24-24BA127ECB8E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953423$37AA0872-75C8-47B0-93CC-FB0AD415C1C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953423$584ED768-B0EC-4814-ADF6-0BC1649B78D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e9cf3724d787f27898cf1a55eec70f229f1b542f","datavalue":{"value":"6171876","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953423$080BE61E-BC5E-493A-972F-89B69C82F3C4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cba4f4e6b1d6add40394622cbe47bbb0afecf1c","datavalue":{"value":"permutation graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953423$6B47144C-FF4D-4CC1-AEF9-EE3EF0FD0890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb1353ab12790402a0ad6cb71373f7556effaa8a","datavalue":{"value":"Petersen subdivision","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953423$AC8113BC-9776-4107-9E2D-F4DBAC22DBB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ae14706edea88a102ee43da4032c363bf1c64c9","datavalue":{"value":"cograph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953423$1C0FF4AA-A18D-4E25-A8C2-3C43E1253CCF","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953423$15953857-E1DB-47A3-88A4-D972EB518FB4","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c4ac0180469a6e4e702e844e4a5b1bf1de2263ed","datavalue":{"value":"bafkreidlxh7bsm4gssw5bgzho3mzs2nve64kqawnenexqv3ritgjekq5yy","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953423$9EA9A3CA-D321-4972-B6AD-F9E6EEF4774C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dffb887defaa53333edaae7ee7509e187040fbc2","datavalue":{"value":{"entity-type":"item","numeric-id":2761063,"id":"Q2761063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c34f8d5946e864b6d9e9d9fc343d36add8a5892","datavalue":{"value":{"amount":"+0.8874794840812683","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1953423$E13C2D74-F0AA-4363-8DFB-3BD8672C18D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b51e9a44f3fe0fa353d2b80ad4ab39f0ca6f2b5","datavalue":{"value":{"entity-type":"item","numeric-id":4351080,"id":"Q4351080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c34f8d5946e864b6d9e9d9fc343d36add8a5892","datavalue":{"value":{"amount":"+0.8874794840812683","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1953423$DC199830-2FE0-4AAE-A2C1-79AB4CBE7E0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c28a1b46df782f7c4e122d5a46fc64d4f2fd6ad4","datavalue":{"value":{"entity-type":"item","numeric-id":1386419,"id":"Q1386419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f39c6f1045686d72fa14ee8abfe40a4653120810","datavalue":{"value":{"amount":"+0.7722302675247192","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1953423$B8A76BE1-3A92-4349-959B-105DF7E5E752","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83979851cbadd5d2ce291f0624d0f7326c78a079","datavalue":{"value":{"entity-type":"item","numeric-id":790849,"id":"Q790849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"804f42d21f0d88a8cc3cf326924d640ec5a7faa8","datavalue":{"value":{"amount":"+0.7403116822242737","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1953423$CBE5BC86-07A3-473B-82C9-4B090457A012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"849b9fafbc209c86d38e435d4eee6bcf733512d0","datavalue":{"value":{"entity-type":"item","numeric-id":4302979,"id":"Q4302979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8eda4f54c847822ba53ae6b7108a5ee01147ee5","datavalue":{"value":{"amount":"+0.738617479801178","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1953423$C04BE520-1D75-4DD1-B70A-747B7489A46A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1953423","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1953423"}}}}}