{"entities":{"Q1612756":{"pageid":1623496,"ns":120,"title":"Item:Q1612756","lastrevid":72341241,"modified":"2026-04-14T04:15:15Z","type":"item","id":"Q1612756","labels":{"en":{"language":"en","value":"Generalized pigeonhole properties of graphs and oriented graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1795946"}},"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":"Q1612756$C2038E46-F59E-4D7C-A2FC-3674CDBF269A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0f823c04039485fc98255aa469d3f477e426c25b","datavalue":{"value":{"text":"Generalized pigeonhole properties of graphs and oriented graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1612756$5AED18C5-8794-48C3-88D0-B155BE3B7A38","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"705b3a8f349564c6b67aa2011e7b53c1a6243503","datavalue":{"value":"1002.05059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612756$4D0B7047-342E-4B75-938B-20DFDB00CF45","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"66ae7b9dc8b554d43e5c1b5b75def0b5fe5aa214","datavalue":{"value":{"entity-type":"item","numeric-id":189716,"id":"Q189716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$0643AA16-1DFE-4376-8ED7-2154BAEF5051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6bc2521eae45715fb417b046daabcb23d4401f14","datavalue":{"value":{"entity-type":"item","numeric-id":241258,"id":"Q241258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$64178E21-56FA-4E89-B69C-89943F9FCBF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"50cca56c6206eec9dbd98ef9e96cdd44192998d0","datavalue":{"value":{"entity-type":"item","numeric-id":231150,"id":"Q231150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$608F1A54-D890-4083-B6C7-9CC8BFF5852B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"422d41f94f8a39580a8eaa67cd40c776a7c16584","datavalue":{"value":{"entity-type":"item","numeric-id":858107,"id":"Q858107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$1BEC1484-E3EB-47C7-89BE-767EF251D903","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$ADE3C443-DCD2-419D-9F9D-03EA77C72A60","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bb93cbd60b6d73fe7de3d4d867e2220ad7d88c1f","datavalue":{"value":{"time":"+2003-01-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1612756$8D0A0FA3-914D-4006-9B72-0F4E3F55B29B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4281a211dc5b4b7c7a80d6b15ea437360555be4d","datavalue":{"value":"The pigeonhole property (\\(\\mathcal P\\)) is defined as follows: a relational structure \\(A\\) has (\\(\\mathcal P\\)) if for every partition of the vertex set of \\(A\\) into two nonempty parts, the substructure induced by some of the parts is isomorphic to \\(A\\). A natural generalization is the property \\({\\mathcal P}(n,k)\\). A relational structure \\(A\\) satisfies the \\({\\mathcal P}(n,k)\\) property if whenever the vertex set of \\(A\\) is partitioned into \\(n\\) nonempty parts, the substructure induced by the union of some \\(k\\) of the parts is isomorphic to \\(A\\). The paper provides the complete classification of countable graphs, tournaments and oriented graphs with the \\({\\mathcal P}(3,2)\\) property. Some contrasts to the classification of graphs with the \\({\\mathcal P}(2,1)\\) property are pointed out. The paper concludes with some open problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612756$D0E673BD-BC42-4D2C-A251-5692ECCDC686","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612756$9314075F-9E7B-49C7-9183-F6F130FF8182","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612756$52E7041A-16D2-4ED3-A069-27B0F935817B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"11d6f17d719a964e5a32daf16135b1261b64689c","datavalue":{"value":"1795946","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612756$BFBEC055-3048-4E67-9B53-2502C7F1F695","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96e2a0e3d1a198019827941c87f338fbd844dcee","datavalue":{"value":"generalized pigeonhole property","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612756$8344A7CE-88E3-425E-946F-0CFC4D24A314","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e62d35d80739c9320588021faca85b02a25ccb7b","datavalue":{"value":"countable graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612756$A3F5F691-BB67-410A-8B7F-9AE0FC09417E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1db92bc7601eaee178ffaed0103e4107bc22c468","datavalue":{"value":"tournament","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612756$486B09EE-75CC-4CDE-A424-A716C7756721","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d88254a5760b31b61e1fb0129d8fa4b56625290","datavalue":{"value":"oriented graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612756$D9562022-316C-4913-AE00-9561E759EC88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8439c3c323b21d48b0e534a0ebe58f84d18c385","datavalue":{"value":"linear order","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612756$F821C089-CBDD-4107-9FFA-7ABA262E62AF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af45ac16b5c3b4cb5ad35340a1e807846a86d0e0","datavalue":{"value":{"entity-type":"item","numeric-id":593274,"id":"Q593274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$03963EC8-ABCA-42A8-B661-CC4D3BE40E31","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":"Q1612756$F9C4705F-541D-4A22-A283-AFD2CA9C73A3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8b025407ad109033bebd7b3b870a427224931c07","datavalue":{"value":"https://doi.org/10.1006/eujc.2002.0574","type":"string"},"datatype":"url"},"type":"statement","id":"Q1612756$8616A483-026F-4A11-9398-E269F23C6AE5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6dd38e1cac3575b599fbfe4e3b931b3c3f4472d2","datavalue":{"value":"W1980496272","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612756$13F615F4-1FA3-4F73-88B8-0A7F165B4E9B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4f46348a670a4e194be43c1dc2240aabbfdaed","datavalue":{"value":{"entity-type":"item","numeric-id":5937580,"id":"Q5937580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$49C80E4C-BA01-4A8B-A617-AE930DE9763C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7446d412e467548cbdfb357161dd8b091ecfc492","datavalue":{"value":{"entity-type":"item","numeric-id":4264540,"id":"Q4264540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$EDADB5A4-9D35-4C67-82D9-75B11A900A20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbd204ba94f86a9467fa4311ddff227495ab29cc","datavalue":{"value":{"entity-type":"item","numeric-id":4761342,"id":"Q4761342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$F292B5EA-7145-4CA1-96AA-A0B09CB90E8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd023fcbc4aefd9be489b2652c47974ece21da41","datavalue":{"value":{"entity-type":"item","numeric-id":1801688,"id":"Q1801688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$A91670FC-A0AA-48C6-B3A3-FCB051230C60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"075385ab0f9cec9e72ad6f715d7267d9b2ed12a4","datavalue":{"value":{"entity-type":"item","numeric-id":3995219,"id":"Q3995219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$34538220-4076-4BC5-9210-32EFA0772F8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b59c0659f3cc2fb18e15dfeb0e452b1db3e9cec","datavalue":{"value":{"entity-type":"item","numeric-id":5689022,"id":"Q5689022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$7146ADD1-6AEA-4322-B7ED-C340A33F368C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"165431b0e6ee7a64a7250c8bc825619390bf26e3","datavalue":{"value":{"entity-type":"item","numeric-id":1182733,"id":"Q1182733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$9DA0A5F0-7AE9-44CD-8A5D-A54E6DE7928E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"225116f3b98655e4cbb084142670e8088acd17fd","datavalue":{"value":{"entity-type":"item","numeric-id":1076017,"id":"Q1076017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$08CC3E52-E5EA-42E9-9E9A-F750BA273268","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bed2aab7de3be42263dd89650394b5c0dea768e3","datavalue":{"value":{"entity-type":"item","numeric-id":3671169,"id":"Q3671169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$F52EF600-567E-4D00-9EC9-A9ECE201A000","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"534730d39bf1b2fb7e127c00d7c04e03699b9f80","datavalue":{"value":{"entity-type":"item","numeric-id":3949052,"id":"Q3949052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$F3F4D704-C535-4A71-8772-D878DE6FF875","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcf3f202451c790f08d61ba232b0e437c1293905","datavalue":{"value":{"entity-type":"item","numeric-id":4284626,"id":"Q4284626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$5D964DEE-8164-4445-A726-EC31325803EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fa7db9c9f645321f9a56cf4f39497857a2113e0","datavalue":{"value":{"entity-type":"item","numeric-id":1357270,"id":"Q1357270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612756$9FE35667-90E0-43B2-94A1-E3DBD26934B7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fd30cc114e909b7b7ef7605ffe1e72c52966165e","datavalue":{"value":"10.1006/EUJC.2002.0574","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612756$EC64D968-74DB-4B8C-AEE8-6A4B23938B9F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d57aff263e91a92454291d3d789305c6e43de08e","datavalue":{"value":{"entity-type":"item","numeric-id":4761342,"id":"Q4761342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b951a2c7379ba073e934f757ecb31205a4bb791","datavalue":{"value":{"amount":"+0.8328976035118103","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":"Q1612756$C22410E8-A634-41E8-B14E-7F9074529508","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7928c55ee68f17a2602dc8b2a0d24df9751fad65","datavalue":{"value":{"entity-type":"item","numeric-id":3689214,"id":"Q3689214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b951a2c7379ba073e934f757ecb31205a4bb791","datavalue":{"value":{"amount":"+0.8328976035118103","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":"Q1612756$2BAB6978-5160-478F-AF8D-BE405FDA91EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6807f11148de719e3547f7263eb0c782f2f1f50b","datavalue":{"value":{"entity-type":"item","numeric-id":4264540,"id":"Q4264540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0634cd29289d8f19cf64768e77a7690afbc3e5c","datavalue":{"value":{"amount":"+0.7863112688064575","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":"Q1612756$602DB564-6AA3-4D62-BED0-3B056088AEBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e41f88c61d6d372217b3505a92f1bf0285e11dfe","datavalue":{"value":{"entity-type":"item","numeric-id":3764175,"id":"Q3764175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1404ead238e95869b2133a617786b00c3c5af1d","datavalue":{"value":{"amount":"+0.7303347587585449","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":"Q1612756$ADA2E131-9F88-4A5A-A101-E104FFFB94F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81f876d35d7fc9b756a364c2bbfa72eb8a5631fe","datavalue":{"value":{"entity-type":"item","numeric-id":3559387,"id":"Q3559387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7f4f07cf7d78d5998c5ea105d15cf1205881ea8","datavalue":{"value":{"amount":"+0.7263982892036438","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":"Q1612756$F1AEF259-C375-4B2B-A1BD-7C33F5E2F85A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalized pigeonhole properties of graphs and oriented graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generalized_pigeonhole_properties_of_graphs_and_oriented_graphs"}}}}}