{"entities":{"Q2761063":{"pageid":2771802,"ns":120,"title":"Item:Q2761063","lastrevid":83144057,"modified":"2026-05-07T06:17:30Z","type":"item","id":"Q2761063","labels":{"en":{"language":"en","value":"Permutation graphs and Petersen graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1682925"}},"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":"Q2761063$79F469AC-B3D9-439E-B2FB-DEE058E6AB7C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c2b12c7c143a5e1fcc2dfe65b43bee8265e4fa08","datavalue":{"value":"0977.05067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2761063$5DFDEA9E-9469-42FB-AD56-7F34E257A51F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"511890414016001f87f67e677ff572f2fd1acbf6","datavalue":{"value":{"entity-type":"item","numeric-id":175515,"id":"Q175515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2761063$1A1BD8E8-CAE8-4331-8451-2CD913111A69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"505aaaa52188a8b6a6be5f2dfa338df09a4c9310","datavalue":{"value":{"entity-type":"item","numeric-id":789401,"id":"Q789401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2761063$B3F5D6C0-FC04-4244-9516-F9DB9F1055D1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dd43b7556960d36e19e31bfdf153901cadf12bc7","datavalue":{"value":{"time":"+2001-12-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2761063$870E9681-11C1-49F2-9DE6-13366573F75A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2761063$CB40BEE7-F76E-480B-A879-D8B30902C72A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2761063$F2B79FCD-9FE7-4B41-BDB5-0F1F4A4819DC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"504b93651866dfdf5d21d871fde5584505581f8d","datavalue":{"value":"1682925","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2761063$E1D6D4CF-CE44-4D42-A001-A49D3B426BDA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cba4f4e6b1d6add40394622cbe47bbb0afecf1c","datavalue":{"value":"permutation graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761063$E3634C3E-031E-45FE-9AEF-61FCDCB81FE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d959bd733318746098f9611a2534b0fcaba0c1f","datavalue":{"value":"subdivision","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761063$42E22E05-3759-49A4-A198-5012B0B8C139","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca453d722b926b8973923e0613afef1c4ab52cf9","datavalue":{"value":"Petersen graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761063$49A3DB8E-235D-42AB-AF7E-9CD795641CE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a35970f6c9d25db8fd6157359f5f87a41735c25d","datavalue":{"value":"edge coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761063$D217FD5B-0EA1-4E70-B56C-8CC598469111","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcf267cbc3e04fdcfc3d3761f7ad8ebdabe8c51","datavalue":{"value":"cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761063$49413131-1BEC-4B35-AAF3-FEB5051227E5","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":"Q2761063$246A240D-38BC-4A55-BE7C-58C52A3756F8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c73323d549eb6e72857c963d3dcc5cba1911745e","datavalue":{"value":{"text":"Permutation graphs and Petersen graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2761063$2321BE7A-B2BD-41DC-AFAD-FBCA0BAD6088","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6f7fbf6651880b9d76c5e78437f7f8284b8f74c4","datavalue":{"value":{"entity-type":"item","numeric-id":6550664,"id":"Q6550664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2761063$4754EB5B-D82D-41B9-A648-A91FCBA82B28","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"101263a11279e3c4f4eb014a8da91fd24f7749e5","datavalue":{"value":"Let \\(G\\) be a permutation graph, that is, \\(G\\) consists of two disjoint cycles of the same size and a matching \\(M\\) between them (so \\(G\\) is 3-regular). The authors prove a strengthening of a theorem of \\textit{M. N. Ellingham} [Congr. Numerantium 44, 33-40 (1984; Zbl 0558.05040)]: if \\(G\\) contains no subdivision of the Petersen graph \\(P_{10}\\) (= permutation graph 14253) then \\(G\\) contains two distinct 4-cycles. In fact, it suffices to forbid only the subdivisions of \\(P_{10}\\) formed by the two cycles of \\(G\\) and some 5 edges of \\(M\\). This is shown to be best possible. A corollary is derived which says that every uniquely edge-3-colorable permutation graph with at least 8 vertices must contain a subdivision of \\(P_{10}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761063$1CAC8CB6-0717-449C-976A-6B389682BD7D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6f1020581485ed0765aa827546a5c57c3b02d582","datavalue":{"value":{"entity-type":"item","numeric-id":627537,"id":"Q627537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2761063$4E43DE08-9789-490E-8F41-FABBCD8E05A0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a69e6de1cb035955f3d0fc30fc9330bda26e09bb","datavalue":{"value":{"entity-type":"item","numeric-id":1953423,"id":"Q1953423"},"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":"Q2761063$D567AFC8-ECBF-4E8C-A3BE-DDC5C8911946","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":"3de7b174b6dcd66643e60700d0e7a3bfb8d81c0c","datavalue":{"value":{"amount":"+0.7482767105102539","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":"Q2761063$17594666-09BD-425C-9C1E-45D206708F93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfe583179647ce6efe655a1831c391cb562f07fd","datavalue":{"value":{"entity-type":"item","numeric-id":3342599,"id":"Q3342599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c3b95692553664e8fb26f5850145807a08c3809","datavalue":{"value":{"amount":"+0.7479125261306763","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":"Q2761063$9DAD2A08-2B81-4CC2-AA1C-BB09F96A4B24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c696978d7efeac2b564e09abc90c355029ecaa95","datavalue":{"value":{"entity-type":"item","numeric-id":1198655,"id":"Q1198655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"986bee51a3d0f61185e298f03da0f512aee62c43","datavalue":{"value":{"amount":"+0.7425806522369385","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":"Q2761063$DCB52910-15FE-420D-9E7C-20E17B4D7182","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":"986bee51a3d0f61185e298f03da0f512aee62c43","datavalue":{"value":{"amount":"+0.7425806522369385","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":"Q2761063$4AC2FDA4-90BB-4E0E-925B-39832E0502DC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Permutation graphs and Petersen graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Permutation_graphs_and_Petersen_graph"}}}}}