{"entities":{"Q2758332":{"pageid":2769071,"ns":120,"title":"Item:Q2758332","lastrevid":47710375,"modified":"2026-01-02T12:13:38Z","type":"item","id":"Q2758332","labels":{"en":{"language":"en","value":"A translation of Gallai's paper: `Transitiv orientierbare Graphen'"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1679716"}},"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":"Q2758332$7B4F3B68-48AB-4D91-934C-5A8CC89FB5E5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d4ca550bebc0d231d46a1908ae155dbb6721b561","datavalue":{"value":"0989.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758332$29633122-991D-4EFA-8733-5C8DCC637F81","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec2d7eb4aa6a054061ffef53b12788916e0dba01","datavalue":{"value":{"entity-type":"item","numeric-id":222618,"id":"Q222618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758332$EAA8A8C2-50EB-4208-A3BE-87A2FD988F32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6eccd330e58db916925e9726f6d3cc506f17a2da","datavalue":{"value":{"entity-type":"item","numeric-id":442401,"id":"Q442401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758332$6FDB1A81-EB86-41C6-A55B-65845A549627","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f7a5494c92a046f682164335d6adb9be84d31ccb","datavalue":{"value":{"time":"+2002-03-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2758332$36FF6A19-DDB6-4A5E-A58F-EF2124BFC08B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758332$F37B151E-A55D-40E4-87A3-A41DBA61478E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758332$78B8A08F-B0BB-480C-B314-294D4D48AC95","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ca323d4969579649f2f7022a2aa489d9629b50fb","datavalue":{"value":"1679716","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758332$98DD149A-90BD-4B81-BA7A-ECFCED40794D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c89639778a113cbe54a2efcba7f98ccd79f62275","datavalue":{"value":"characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758332$F138EF5B-1487-49A9-9D41-6951DB567C08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f801af849bb8c30c3577c546e2e3e485502ec8b","datavalue":{"value":"transitively orientable graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758332$92BE1F17-E3D7-4F6E-A3FF-9A3E8B0E0613","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758332$0F47919F-A347-4A93-8ECF-0689B1DCB9C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b5ec4bfc180eae10430884638106ed242afd207","datavalue":{"value":"testing graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758332$0B5F93B8-9ED6-4698-81B9-5F9478DFE6FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa48b037302c6763292e9a21faca4067a4de99a1","datavalue":{"value":"transitive orientability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758332$9A31BDBC-5CE4-4021-90BC-9FE04D331EF2","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":"Q2758332$F1225646-3FDB-41EC-B054-0214DFF921F4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"07ffc5f1771932e7e86d4c5db40ee2b706631607","datavalue":{"value":{"text":"A translation of Gallai's paper: `Transitiv orientierbare Graphen'","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2758332$C27508C6-E935-446F-90B5-AE160531911E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a681c6f291817b23663cbfbabe82e43b77757bac","datavalue":{"value":"This is a very faithful, but not always verbatim, translation, with modernized notation, of Tibor Gallai's fundamental paper on transitively orientable (or comparability) graphs [Acta Math. Acad. Sci. Hung. 18, 25-66 (1967; Zbl 0153.26002)]. Gallai provided a characterization of transitively orientable graphs given by the list of all minimal nontransitively orientable graphs, as well as important structural results valid for all graphs. He proved that a graph is transitively orientable if and only if an auxiliary graph is bipartite, and he described a procedure (which is seen to be polynomial-time) for constructing this auxiliary graph. The only non-trivial step is the computation of the connected components of the neighborhood of a vertex. Thus Gallai explicitly described an algorithm for testing graphs for transitive orientability. The translators provide a brief forward, in which they cite relevant literature.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758332$E40D58EC-89A8-4D5F-9EBF-297EDE7621F3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"205b6d05d63e09819854956633396177079e7ebb","datavalue":{"value":{"entity-type":"item","numeric-id":591987,"id":"Q591987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758332$022917C3-FB82-4202-93D7-50541F14ED74","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f54855a7a2820cc600afa5a0b0c34adbdb0b4ce","datavalue":{"value":{"entity-type":"item","numeric-id":4525261,"id":"Q4525261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c783154d5068e0c0029cad12f87d32a91584eb5","datavalue":{"value":{"amount":"+0.8062509298324585","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":"Q2758332$E63AB4DF-8D9C-4E17-9113-B7DD234595EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbef618e3bd0cb91e237711c0d3f81b704a3f381","datavalue":{"value":{"entity-type":"item","numeric-id":5459137,"id":"Q5459137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5aaf0c4326c689fcc0faac0ac78dae91e4a61df8","datavalue":{"value":{"amount":"+0.8050347566604614","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":"Q2758332$B31F24E1-0F29-4617-A796-E2BDB2CF1137","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69a6ccbe9e844437d975abd4f5cffeeb5ac8d0ad","datavalue":{"value":{"entity-type":"item","numeric-id":3685215,"id":"Q3685215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e0b176b024292defe967de172522b805ec8d963","datavalue":{"value":{"amount":"+0.8045932054519653","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":"Q2758332$9DD68F3B-C692-4E0D-83AB-B30666571D7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"443247248c23a9c1eafa66b8c7fd463751b65ab2","datavalue":{"value":{"entity-type":"item","numeric-id":2476257,"id":"Q2476257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f42e106c7cac565c915b51b053a34d89b2b1b920","datavalue":{"value":{"amount":"+0.7873845100402832","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":"Q2758332$53F0A9F1-1FC6-42A8-ABC5-D3258930CF47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2cb613a9efdb89cdc34e23b60575d454c947408","datavalue":{"value":{"entity-type":"item","numeric-id":3712352,"id":"Q3712352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a7c9660d081e59dcf77e07c95fa456f47d7d41b","datavalue":{"value":{"amount":"+0.786952555179596","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":"Q2758332$E591110C-2D2E-4284-B1D1-147227D2FE98","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2758332","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2758332"}}}}}