{"entities":{"Q1080439":{"pageid":1091191,"ns":120,"title":"Item:Q1080439","lastrevid":42861925,"modified":"2025-07-15T12:08:41Z","type":"item","id":"Q1080439","labels":{"en":{"language":"en","value":"Bipartable graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3966127"}},"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":"Q1080439$7924DB6D-D506-4186-8326-9DB3D08D934E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"770cf889f9af9c0b03ad13c92a5811969269c844","datavalue":{"value":{"text":"Bipartable graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1080439$1F91CDF8-54D0-421D-8F18-86DFB106244B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5beefa43ae7722578326344e5b03a0bd4a37dbca","datavalue":{"value":"0599.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080439$5F4B8638-D97A-427F-AECA-B9FD058B42D7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"af4bfae8d3be7cb3a8cc5c0d34d24b28cbb9332f","datavalue":{"value":"10.1016/0095-8956(88)90050-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080439$882DF667-EF6C-4A21-8052-514FD74D9C52","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83acb26c132edffe3503227fdedd09777c685939","datavalue":{"value":{"entity-type":"item","numeric-id":1060191,"id":"Q1060191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080439$1FD0FFE9-1CE7-444E-B8ED-DC9EC2A3D8BE","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":"Q1080439$695913FD-DEA4-488A-9C80-3430DBA9CF44","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1080439$EE20023A-8C2D-455B-947F-3532EF04A6C9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9500ee92926b028ffcb3c6121c3d5515f7150ab8","datavalue":{"value":"We consider a construction which associates with a graph G another graph G' such that if G' is a bipartite graph, G is perfectly orderable. For such a graph G we give a polynomial algorithm for an optimal coloring by delivering a perfect order on his nodes. This class of graphs is shown to be different from the known classes of perfectly orderable graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080439$8001E0C2-F60E-41AC-BAA4-14B8813698BC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080439$F5C589C0-6C70-41FA-B6F4-BD76CEA84018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080439$F7436FA1-C104-4198-87FF-1E0264F46B71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080439$C46604AB-74F0-48D7-A803-30458B4AEFD1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"268364a95858fa88f0ad549a41886b192aedca9c","datavalue":{"value":"3966127","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080439$038DA35C-8BE1-4C79-88A5-FE39A3523A7B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080439$E49420C4-EE79-48DA-9CD6-78AA4443F71A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080439$D07DD351-3A8E-4F08-B6C7-69678120D7A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3351172f2b5cf302b9b348337fc5ce4204fdd25","datavalue":{"value":"optimal coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080439$308DAC63-C4A8-44FA-BD0A-2A0E94FA254B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1299386ebc4f612e1fffd660722437a77f37e1b6","datavalue":{"value":"perfectly orderable graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080439$77C2BB90-54A3-4ABD-897F-C61DA5B7DD8E","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":"Q1080439$34EA6E28-4BA0-4926-B268-FBDE172CCFCB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4de6498e1d156dbdcbfbe60159d4b16b5db39772","datavalue":{"value":"https://doi.org/10.1016/0095-8956(88)90050-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1080439$9AD0F7FB-9579-456D-97FF-D90364258A10","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cc440290a42e81493d79bccefddad452cbf49ef6","datavalue":{"value":"W4213049991","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080439$ED3D5D88-C7CE-48FF-B63E-BD04A8B4E51A","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":"Q1080439$94D15FEE-000F-4651-A6CB-F6EF4E39EDA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98d84d8d1a6e846802c9d13beeae73d688fdc4b4","datavalue":{"value":{"entity-type":"item","numeric-id":3356337,"id":"Q3356337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080439$F2D735A9-56E2-4319-B397-5780596F4A7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbc1cbf254c6eb54db676c3af43bf0720c8750ac","datavalue":{"value":{"entity-type":"item","numeric-id":3798703,"id":"Q3798703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080439$991A8C16-D7B9-4203-9776-4C03A26F89CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff9d52868be71e302f41a020cd3dde1ae69f41aa","datavalue":{"value":{"entity-type":"item","numeric-id":3800062,"id":"Q3800062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080439$D9702CAE-79C2-4A17-9AA0-CC74D30E3A6E","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":"Q1080439$BDF54BAD-3637-4CB4-98B9-79E6ABA3D74B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2990a0db87776ed70786579ac6086b0d79e7b6ee","datavalue":{"value":{"entity-type":"item","numeric-id":2334080,"id":"Q2334080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8460f6c1c2e9dea4a185dc6ed3610eaa86920126","datavalue":{"value":{"amount":"+0.96272695","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080439$52AF59F4-67AF-4731-B47D-29BBE9910A59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc77cfe7e35cfec97bc169a690803774b289f3b0","datavalue":{"value":{"entity-type":"item","numeric-id":688258,"id":"Q688258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb26754c688944ef43f4119b5f863c8ce7ce55a7","datavalue":{"value":{"amount":"+0.96233004","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080439$0E97B998-B95E-467E-AC9B-955391C9DA5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75a43f2caa0e06eee97f33910c224dd7117818e7","datavalue":{"value":{"entity-type":"item","numeric-id":1343223,"id":"Q1343223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4b021bff1145dec5b4e98e933562edf81a3b878","datavalue":{"value":{"amount":"+0.94541156","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080439$0DB99CE1-1493-405A-BE19-1B1A6A0240CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fc2e951b7231c438a533d23fc6b06aac7ea5cfc","datavalue":{"value":{"entity-type":"item","numeric-id":2563506,"id":"Q2563506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0618364ecf44731696401fc80d33817e6a30ce94","datavalue":{"value":{"amount":"+0.94464254","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080439$BDC7604D-E7EF-4B2C-8A9A-D82CF1BCFB32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"381a439b9872d093552c711581fccec02aa22f2d","datavalue":{"value":{"entity-type":"item","numeric-id":2568470,"id":"Q2568470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5229f0c6183910b8408ef97ad5e137d2b39ac83","datavalue":{"value":{"amount":"+0.9372526","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080439$6783EE6F-9CD2-40C3-A4D4-9ECCD4ADDFB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1239cf799f9b49de994dfbf45e250e846c7226c1","datavalue":{"value":{"entity-type":"item","numeric-id":4208001,"id":"Q4208001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d42a991b648920aec2da304bc304ee1ce220d20f","datavalue":{"value":{"amount":"+0.9264076","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080439$7C2E162A-DB26-4232-88E5-906D591FF948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b22eb8cd50d3fb6d44ca20201f6993611910ce67","datavalue":{"value":{"entity-type":"item","numeric-id":3509720,"id":"Q3509720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d42a991b648920aec2da304bc304ee1ce220d20f","datavalue":{"value":{"amount":"+0.9264076","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080439$0CEB9F1A-C5A2-4AE7-A2FF-8069D16B00F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f11b00e49568a182fc84ed2035379833035e55c","datavalue":{"value":{"entity-type":"item","numeric-id":2741321,"id":"Q2741321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2e32a3822b447a77e1a42a39c0e9938d35ea5bb","datavalue":{"value":{"amount":"+0.9235883","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080439$FAEE9D85-1F90-4FF0-864D-038629C27D29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"988f29a8389d780f8fd0dffa602b907c828e4fb1","datavalue":{"value":{"entity-type":"item","numeric-id":1811078,"id":"Q1811078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acff9a8455a1a68daab14431b5dd87783dea7f5e","datavalue":{"value":{"amount":"+0.92358816","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080439$58A7FE9E-5D1D-463B-9972-6427311044C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09a2cb942606d9fa48e9d7de67450e802529e369","datavalue":{"value":{"entity-type":"item","numeric-id":796548,"id":"Q796548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2be0d3efe84c96a4f2064a8548de6b697f860b4","datavalue":{"value":{"amount":"+0.9232887","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080439$DB8C54C9-A1FE-4684-955F-AED73336A7D1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1080439","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1080439"}}}}}