{"entities":{"Q1815322":{"pageid":1826064,"ns":120,"title":"Item:Q1815322","lastrevid":69032163,"modified":"2026-04-13T03:51:48Z","type":"item","id":"Q1815322","labels":{"en":{"language":"en","value":"Properly orderable graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 943229"}},"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":"Q1815322$4F41CF1B-0A84-47D0-84EE-1DF92657EED4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0db7e6644bc13006b83a8558b47ef024618c852d","datavalue":{"value":{"text":"Properly orderable graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1815322$B38400A6-62DD-45F5-9CCE-F87B49E3B5B6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ddf7d8259785da30816c1eae34f6c4c14b95cdb2","datavalue":{"value":"0859.05062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1815322$9E6493A2-AA8A-4B97-AA9A-CA2270181D4B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ed614c5c0e2b5f48931a908b926d33490c549002","datavalue":{"value":"10.1016/0012-365X(95)00045-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1815322$CE70C083-9C09-49F9-BC14-CB5F8CC72BED","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3d173afbda7d364ee20fa0af1c6602b56374da2","datavalue":{"value":{"entity-type":"item","numeric-id":187141,"id":"Q187141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1815322$89017442-5B4D-4E93-A54E-CE34FD9483CB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1815322$BA54C65F-902D-4A64-AB3B-CE373F4A7B1E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"987a2f2e82526aa2085dc97bf2e88574c6b234f8","datavalue":{"value":{"time":"+1997-04-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":"Q1815322$F04C921A-E85E-4E54-BA6A-9DAE13E886BA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7ed5f632b8328455a4cd3764e877a89474657568","datavalue":{"value":"In a graph \\(G\\) provided with a linear order \\(<\\) on \\(V(G)\\), a chordless path with vertices \\(a\\), \\(b\\), \\(c\\), \\(d\\) and edges \\(ab\\), \\(bc\\), \\(cd\\) is called an obstruction if both \\(a<b\\) and \\(d<c\\) hold. \\textit{V. Chv\u00e1tal} [Perfect graphs, Ann. Discrete Math. 21, 63-65 (1984; Zbl 0559.05055)] defined the class of perfectly orderable graphs, i.e., graphs possessing an acyclic orientation of the edges such that no obstruction is induced, and proved that they are perfect. In this paper, the class of properly orderable graphs is introduced, which is a generalization of Chv\u00e1tal's class of perfectly orderable graphs since obstructions are forbidden only in the subgraphs induced by the vertices of an odd cycle. The perfection of these graphs is proved, and an \\(O(m^2+mn+n)\\) optimal colouring algorithm for the class of properly orderable graphs of order \\(n\\) and size \\(m\\) is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1815322$02312B6E-88C4-4DD0-AC70-52FBDC4AAE55","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1815322$C117808C-BE95-442F-9D33-96C9143A0CC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1815322$547D8E9E-9FEB-4125-B02F-3A0542C05014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1815322$061EB5C7-2121-488E-A37B-D1CC1D09F181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1815322$C01633F7-206B-4933-A711-0FAFC31C587B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"818ee4366447d22118992cad1bf986fc19c6b138","datavalue":{"value":"943229","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1815322$89D5FDF6-A7B4-43D7-B0D1-3C97E1F51FB5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"840dabfcb28ecf686ad265142fee855482066e02","datavalue":{"value":"obstruction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1815322$FE2E6EE7-4ECC-4B21-A144-17409FBF9E2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1815322$0FF82797-E03C-4E8F-9B0F-50F5E1D6CE8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1299386ebc4f612e1fffd660722437a77f37e1b6","datavalue":{"value":"perfectly orderable graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1815322$78BA07F4-67D3-425E-8BEE-1332B1C28BA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad6e3bcaf20998a8f9ca6404afe6fbe91bcc5aa4","datavalue":{"value":"properly orderable graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1815322$0BEA695E-700D-4253-8055-46209D3914A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be8df57be8c106df4fbe375ad2ff9851f149c079","datavalue":{"value":"colouring algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1815322$1D4BEDCB-CC9C-4F7C-9155-2BBFE712C9F3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1815322$7900ACF6-2123-4EB3-95D3-600D932EC691","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":"Q1815322$1D9717CF-0E60-4108-A53F-B75479ACE0EC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f091a2487faa4320a607c7fc5ddd1d40ffc78957","datavalue":{"value":{"entity-type":"item","numeric-id":5615282,"id":"Q5615282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1815322$EC5304F4-4598-470C-AF90-5AE46419C207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9bd269295ba877c106cd58908caf0f087a4411b","datavalue":{"value":{"entity-type":"item","numeric-id":3347930,"id":"Q3347930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1815322$F85FD97D-4BC2-4C78-AEA3-853B42581865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d805d39c87d3dd9dd3ce670f5624942a5527159","datavalue":{"value":{"entity-type":"item","numeric-id":1089007,"id":"Q1089007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1815322$88EE1F98-B53A-49ED-AB31-F6231E521CB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f14929504188a53ef660023bd30753f8781f60c","datavalue":{"value":{"entity-type":"item","numeric-id":1104342,"id":"Q1104342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1815322$C582784D-EEB3-4A67-BAFC-846077E1F264","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c262c7eca9e2144a42b7bec58fdd3a6233dafa8","datavalue":{"value":{"entity-type":"item","numeric-id":3831058,"id":"Q3831058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bcec9d333b1c3ff922505147957a46dade2ecc6","datavalue":{"value":{"amount":"+0.8461728096008301","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":"Q1815322$D42947AD-1F3A-4AE4-AE26-CFF572F45345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10ae09667ceba9715d22199702e34348eab1cc42","datavalue":{"value":{"entity-type":"item","numeric-id":3800062,"id":"Q3800062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a29213e51f76b8cf27b09b6c859fef652dffaff0","datavalue":{"value":{"amount":"+0.8439005017280579","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":"Q1815322$8B104186-55B2-46F5-BC26-E4A0C2E1A3EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8b5817a1a58b871578bc06d6363b498af73d03a","datavalue":{"value":{"entity-type":"item","numeric-id":5959094,"id":"Q5959094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ddc400dfe2c502984e13b7dfa20bab542d04592a","datavalue":{"value":{"amount":"+0.8437199592590332","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":"Q1815322$FDD54E39-0A2E-4A3E-94CC-ED05F4BE2C9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed9ce4ffb0ddd9ddb3311487862d870dcdde1d01","datavalue":{"value":{"entity-type":"item","numeric-id":918707,"id":"Q918707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ddc400dfe2c502984e13b7dfa20bab542d04592a","datavalue":{"value":{"amount":"+0.8437199592590332","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":"Q1815322$377CB454-7CCC-460C-9DC7-65551AEDA0EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10d66cd627bcb6c7465f57b503cd14da6349956d","datavalue":{"value":{"entity-type":"item","numeric-id":3347930,"id":"Q3347930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf33590408edc0e7fcf101b213bab5cf97e314e9","datavalue":{"value":{"amount":"+0.8268851041793823","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":"Q1815322$28C4DAA5-ECF2-41FF-8BA7-F1F824AFA28D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Properly orderable graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Properly_orderable_graphs"}}}}}