{"entities":{"Q1089007":{"pageid":1099759,"ns":120,"title":"Item:Q1089007","lastrevid":69938532,"modified":"2026-04-13T11:21:21Z","type":"item","id":"Q1089007","labels":{"en":{"language":"en","value":"Alternating orientation and alternating colouration of perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4002135"}},"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":"Q1089007$E09ACE70-9747-44F1-957A-47AA5BE30AB7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"95b1c38bc75ff998fd797abf2c97aa6dcb1d4e0b","datavalue":{"value":{"text":"Alternating orientation and alternating colouration of perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1089007$6B25252C-8937-40F0-BDA5-0B17A4F6ECC9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"da093fac5948f6c57302f8cdcb6d0fcd59263bf8","datavalue":{"value":"0618.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089007$300A43AF-BBC0-4E37-BB48-75AB02369E3C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"30a51b6789f7ec95f1803d222db2c93ffb2c352e","datavalue":{"value":"10.1016/0095-8956(87)90045-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089007$DBFBDEAB-0774-4508-9AB5-6C9774B3D8EF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$5627FB2A-7332-4704-84F8-80D62716B236","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1089007$F2256949-486F-44E6-ABEE-B3B3A567EF66","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9f1aa0ff04383e0e82db939721ee0ce68ff1a88f","datavalue":{"value":"In this note are introduced the terms of alternating orientation of graphs and alternating colouration of graphs, and at first in Theorem 2.2 the important property is proved that in a minimal imperfect graph each path \\(P_ 3\\) with three vertices extends into a hole. By using this property the author generates two classes of perfect graphs and he shows:    - Every alternately orientable graph is perfect (Theorem 2.1),    - Every alternately colourable graph is perfect (Theorem 5.1).    It is shown that the first class contains all comparability graphs, all triangulated graphs, the i-triangulated graphs and such graphs G which are union of two threshold graphs, and the second class contains all triangulated graphs and all line-graphs of bipartite graphs. All these terms are defined and they are described in a clear manner. Furthermore it is shown that certain well-known classes of perfect graphs are not alternately orientable, and vice versa. Finally the author develops an algorithm which allows to determine whether a graph is alternately orientable respectively alternately colourable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089007$21851BBE-F48A-4DD9-9DDC-80496BE85417","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089007$2621A297-99AB-4CAA-A81B-E43926D60917","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4ac09be63e228344fc300b32de680fa71fb56f42","datavalue":{"value":"4002135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089007$C18E0BE7-F095-4379-8D32-7EB516B202AA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04423303d06d3e360f7b27599493e56854b031ab","datavalue":{"value":"alternating orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089007$D4ECEE64-D6BB-43D8-AC67-1D97020211F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e506edc5e04505a5d8de4ad46d74f140600b4f9","datavalue":{"value":"alternating colouration","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089007$C206D4BA-DC37-4F1B-8845-5FCE6A48A9DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f90132bc054d5daef6613568ce642098c0512892","datavalue":{"value":"classes of perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089007$C3133A9C-AB57-4E9B-AE4E-080367756A83","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7598b946dc98bf1d17807d2ef3a244f2419361f8","datavalue":{"value":{"entity-type":"item","numeric-id":234396,"id":"Q234396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$73EC79E9-F174-4209-B05D-99803675A111","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31cef456e8646accdc28b523a232a52220366047","datavalue":{"value":{"entity-type":"item","numeric-id":593309,"id":"Q593309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$98709D12-3D5D-4F64-BE52-8AD1A9012377","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":"Q1089007$8BB6CA84-CD2D-48C3-B611-834ECFFB9C68","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"921107394fea379e659490021b952818013f557d","datavalue":{"value":"https://doi.org/10.1016/0095-8956(87)90045-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1089007$4238D0A8-9DE0-42C7-87DB-E643FEE92938","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9f47b36c9709d4925f3b456eb64a75944f6bf22a","datavalue":{"value":"W2041933132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089007$3200E400-C555-452C-981C-500BBC2A67D8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8a74f042ba1f29a12a670ab9d659cf777707121","datavalue":{"value":{"entity-type":"item","numeric-id":798301,"id":"Q798301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$6490C5C7-5161-4F32-8EB2-4CC445C6A657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2d67bd3980ca4eba682fae6d5244771f4d9299e","datavalue":{"value":{"entity-type":"item","numeric-id":3222875,"id":"Q3222875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$6FC7256C-0AA3-49C0-BB9B-3FC361085C37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8439cd84a49b5225dfa76205f17bb5321104a88b","datavalue":{"value":{"entity-type":"item","numeric-id":3222886,"id":"Q3222886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$96B28E0C-2DD9-4CA4-9075-B488747DA3F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"377fc7d6f0f87cd999526d782ba240d822d49abd","datavalue":{"value":{"entity-type":"item","numeric-id":1121289,"id":"Q1121289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$74B6C9B5-BA92-47A3-BA6D-F116B4D93792","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":"Q1089007$471C1699-FFEF-4531-8487-0F4D9ABD44A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7f3be34444b87e94060eeddaad78e0c69a90fd2","datavalue":{"value":{"entity-type":"item","numeric-id":4165164,"id":"Q4165164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$2839A8B5-980E-4CC2-B54A-160D0EE883F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4af1dfbef55e5c6f877defc758d39f47fcfc762b","datavalue":{"value":{"entity-type":"item","numeric-id":1118619,"id":"Q1118619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$02B46C0B-69A1-4EF8-83CB-4CB7DD064E0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"007c64cb1e51e420a82b1528582743678952b922","datavalue":{"value":{"entity-type":"item","numeric-id":2648578,"id":"Q2648578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$87E1495C-ABAF-4CDB-9EC3-DDFC18E82B33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1f4712fe0e4365ae43e7804a03e54faf57f0513","datavalue":{"value":{"entity-type":"item","numeric-id":5341588,"id":"Q5341588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$0FEBE5CA-3436-4823-A288-C5DAF53A5138","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8539d1fcf3cff5fbb08dd6973662b887ad57892","datavalue":{"value":{"entity-type":"item","numeric-id":5534028,"id":"Q5534028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$6EFA44A7-B7F3-48F1-9BBA-B729AA9FD0B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78fcefc7eb6db493b1640335979e0e48c2971f01","datavalue":{"value":{"entity-type":"item","numeric-id":3291037,"id":"Q3291037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$134880C8-1CF5-49C7-8298-A35C918A326B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ddcab77cc06a1867f1053994ad87177b46c2d8a","datavalue":{"value":{"entity-type":"item","numeric-id":798675,"id":"Q798675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$5F57EFDE-C566-4184-B209-B95C5E55C837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b276fdb2188dac0c4b19127d85e1049cb332b2c","datavalue":{"value":{"entity-type":"item","numeric-id":801088,"id":"Q801088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$7169F832-9454-43F2-9250-753E0AD48B71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bed7197995b093007527a5d546d60b05148a6d9e","datavalue":{"value":{"entity-type":"item","numeric-id":1822967,"id":"Q1822967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$6100F08D-31BC-403C-8A10-BB4EB6930054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"848565b0c2025ab3a53b83ed30a366727997e5e9","datavalue":{"value":{"entity-type":"item","numeric-id":1096652,"id":"Q1096652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$9A0646F6-3B86-47D6-B0DB-67F12653B62D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4ecc018fdb7c46440581e7f9a880e328ca21441","datavalue":{"value":{"entity-type":"item","numeric-id":1248633,"id":"Q1248633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$75455933-DA41-46BE-98B8-44AB8D44782B","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":"Q1089007$18587D81-59FB-4504-8845-7D427A9445FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c370d2f97b9355d875c3e7ba84e74a18ad9fb876","datavalue":{"value":{"entity-type":"item","numeric-id":5596090,"id":"Q5596090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$70F27791-4345-48A6-9724-F13D4F97B531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fa193218207eb38d51fb6f176c0a7414082b867","datavalue":{"value":{"entity-type":"item","numeric-id":3347929,"id":"Q3347929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$D0CE08B0-F342-4A2B-A542-4C5F1E2C95B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46cea1204e8b56e8cdf89cf3b32e1a95f1f87fb2","datavalue":{"value":{"entity-type":"item","numeric-id":1213881,"id":"Q1213881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$FBC00460-E55B-4A03-AC9B-5DDD8A68BCB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54dec574b0c5e7327d705b995c5ee1dd4628ec94","datavalue":{"value":{"entity-type":"item","numeric-id":1171076,"id":"Q1171076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$840FDC84-59FC-4946-A33B-536367114C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b05636f797e670c0b724b22e9db1e87e8fe2110b","datavalue":{"value":{"entity-type":"item","numeric-id":1245851,"id":"Q1245851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089007$DCB6C5CA-F6F2-4846-B594-D4454B399944","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4add5281769213f2043556c93c255714beedfd3","datavalue":{"value":{"entity-type":"item","numeric-id":1112847,"id":"Q1112847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3ccf22e24c710c461f36e3646c2bdbb7861c033","datavalue":{"value":{"amount":"+0.7889050245285034","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":"Q1089007$751383F7-56AE-466A-9270-E3F0621E5DDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a6b7d84eada630f098ce79a700b93f07bf9e7e9","datavalue":{"value":{"entity-type":"item","numeric-id":1104342,"id":"Q1104342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53330372dfc54adf260aa20b94c6bd9e9d99dba3","datavalue":{"value":{"amount":"+0.787922739982605","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":"Q1089007$F75C6D6A-7B1E-4F16-A0AE-CF55249AF8D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fa303011353dedefdefdd44f491078358d4bf68","datavalue":{"value":{"entity-type":"item","numeric-id":3351379,"id":"Q3351379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b1aa413fed3e0efa1810876b6a08a23d1f19bc0","datavalue":{"value":{"amount":"+0.7817943096160889","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":"Q1089007$EBF6B875-F400-47DE-BF95-7D4D62403C66","rank":"normal"},{"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":"cd9a9c2fdc9e2822ad5c53ebd4c43ba1fdb8064c","datavalue":{"value":{"amount":"+0.7808769941329956","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":"Q1089007$CAE5B7F8-F859-4798-A991-56BE9EA16C51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"892eafb07e69706c0f9e30bd9a85059cda0c982e","datavalue":{"value":{"entity-type":"item","numeric-id":1403295,"id":"Q1403295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25072cdf19f0d1025ebdc864805fde4de49ead82","datavalue":{"value":{"amount":"+0.7803905606269836","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":"Q1089007$B38C8EC8-95D8-443B-8320-6CB4F81ED1D1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Alternating orientation and alternating colouration of perfect graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Alternating_orientation_and_alternating_colouration_of_perfect_graphs"}}}}}