{"entities":{"Q686245":{"pageid":688094,"ns":120,"title":"Item:Q686245","lastrevid":63608643,"modified":"2026-04-11T14:19:38Z","type":"item","id":"Q686245","labels":{"en":{"language":"en","value":"Which claw-free graphs are perfectly orderable?"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428102"}},"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":"Q686245$42E28B31-A0F3-4B29-82A3-29E641B01D74","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"02602a0f843af4482f641c9a2fb4684a7b9824e3","datavalue":{"value":{"text":"Which claw-free graphs are perfectly orderable?","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686245$872AF491-B060-4E70-AC73-A025529A4434","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1c31053b79a4227ab7dc2febaef6685dff02646d","datavalue":{"value":"0783.05086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686245$3D6D0756-0125-4046-8A12-58612C869F43","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7a71d6a1663c0333cb3a4837537a670c32ea9679","datavalue":{"value":"10.1016/0166-218X(93)90221-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686245$CE61C608-A70F-4AB1-B5E8-815FD8ED44D2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"42c33d3d516bcf7a7a7968560a1817b77f2fffdd","datavalue":{"value":{"entity-type":"item","numeric-id":641184,"id":"Q641184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$21C4BDB2-631C-4107-9378-B2C4B3FCB43E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$A9290125-DA65-42E3-9F51-FFCD3BB3794F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f67bd20fe430f6951bd39751d5694c2262cae6a7","datavalue":{"value":{"time":"+1994-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":"Q686245$D19FC4CB-6C09-4F4C-8650-3AF21E0A5E32","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"17e67d67ef5af58fdc730249c601ed34094edc26","datavalue":{"value":"Given an undirected graph it is perfectly orderable (p.o.) if it permits a perfect linear order \\(<\\) on the vertices, i.e., one such that no chordless path with vertices \\(\\{a,b,c,d\\}\\) and edges \\(\\{ab,bc,cd\\}\\) has \\(a<b\\) and \\(d<c\\). Since p.o. graphs are both interesting graphs and since recognizing them is NP-complete, determining subclasses (along with suitable algorithms) which may be determined in polynomial time is quite useful. P.o. line-graphs have been so characterized by the author. The class of p.o. complements of bipartite graphs has also been among classes characterized in this manner. A claw is an induced subgraph on \\(V=\\{x,a,b,c\\}\\) with edges \\(E=\\{xa,xb,xc\\}\\). It is shown that line-graphs and complements of bipartite graphs are claw-free. Furthermore, a complete characterization of p.o. claw-free graphs is provided by describing nine infinite families of forbidden induced subgraphs and in the development of the proof of this important theorem the wherewithal for a polynomial time recognition algorithm on the class of claw-free graphs is also created. As a byproduct a generalization of the characterization of totally balanced matrices found by Anstee and Farber, Edmonds and Lubiw, Kolen and Sakarovitch is immediate via the observation that this characterization is precisely the case of complements of bipartite graphs in the present setting.","type":"string"},"datatype":"string"},"type":"statement","id":"Q686245$7ACA31F3-5C53-4FAF-9F88-5689A2FDF435","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686245$243F0D5F-8C88-4DEE-91F1-65889EB6FEB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686245$4C3E5D3A-5D78-4347-98CA-04BBBB300EDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8f1bdd4f16c3aeb170f7a029744527559b7f1b57","datavalue":{"value":"06F99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686245$42969D06-2A3C-46A9-898D-E0C5C1C16D92","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a7d3bd60d8751bd13ca5c1fc2f382abecdbadbaa","datavalue":{"value":"428102","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686245$1C05C0E5-65B8-4C42-AC39-039446EAE38A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68ad50291a1df55b8fbde4706410c9b99f37dd90","datavalue":{"value":"perfectly orderable","type":"string"},"datatype":"string"},"type":"statement","id":"Q686245$9373804E-B441-40B6-99F0-4D90E7BF1297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d50f7c6a057e062a134e078d1140b901e5720d5f","datavalue":{"value":"perfect linear order","type":"string"},"datatype":"string"},"type":"statement","id":"Q686245$74D98E6D-DE81-4E4A-9CE3-5283C7346FEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q686245$5E8A1424-E290-46E2-A4EA-5B0284845CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68b4d35fcda914792f11b716ca628f90028fc21a","datavalue":{"value":"claw","type":"string"},"datatype":"string"},"type":"statement","id":"Q686245$6D4A7E64-2495-428E-9D73-7C327E469078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a116c5bca925e8632183a65f3061f40ab231ceda","datavalue":{"value":"line- graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q686245$4B723EEA-42FA-4627-A243-E957CD0166BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e7504dd92d8676e48627acb306cf4f2856c146d","datavalue":{"value":"complements of bipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q686245$9C58A0A7-1CAC-466A-8B64-EFBECADEC156","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf2bdc388a8c2bee548ba5c2acc5f66c693118c4","datavalue":{"value":"claw-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q686245$31B55583-7FD6-465D-BC07-F63758B3DE37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c89639778a113cbe54a2efcba7f98ccd79f62275","datavalue":{"value":"characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q686245$F3263E4D-C0CF-4C6A-AC06-F720F51C0E40","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b626688718ca3d61fce8479b1c17fa40d92d8dda","datavalue":{"value":{"entity-type":"item","numeric-id":233347,"id":"Q233347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$D4BC75FC-CEB9-47FE-82A8-680D02969D9F","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":"Q686245$7BDF09E2-B21F-4B28-A754-F3C716A6A6C3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b717ce5476163967b0df9674233704df8f3864c4","datavalue":{"value":{"entity-type":"item","numeric-id":3344216,"id":"Q3344216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$92AC058C-EB4F-4897-A7B4-2A7F13277C21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0fe6ea96ca8b0d0a6de26c3054a97527553f7f1","datavalue":{"value":{"entity-type":"item","numeric-id":686245,"id":"Q686245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$82E4B9FC-B459-4EAD-BEA1-A1489C310402","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":"Q686245$7C165FC1-4346-4D1A-B338-5565FDF03F0A","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":"Q686245$0A925881-786B-4BFD-AB19-A2BB213D40A3","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":"Q686245$292C7F65-7618-4D0D-B0AA-CD6928820BD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b43e3e48b388828a7b8aa17c3f81b7b754c93ecd","datavalue":{"value":{"entity-type":"item","numeric-id":773621,"id":"Q773621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$A985ECBE-83C6-43AA-9160-0B99F6438DB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d20d43981ea8728a5c02a1bf60e0f2b91181b43","datavalue":{"value":{"entity-type":"item","numeric-id":788002,"id":"Q788002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$FC4C6302-770A-4994-A746-9DD2339E72A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0ece15467bc23894a613f0b993db5aadb3fd45","datavalue":{"value":{"entity-type":"item","numeric-id":1080439,"id":"Q1080439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$0648B083-44E4-40A5-A657-065400CBD630","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":"Q686245$44045D92-353C-4F2F-9E83-36F027A496C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67fef302867ce6627490d0936fb4026db5b05da9","datavalue":{"value":{"entity-type":"item","numeric-id":1121924,"id":"Q1121924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$A3DA1CA1-FFC6-4A39-BBC9-7EFB47B46348","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbe76e0762ef700f0ca9d7f733f0d5ad37484351","datavalue":{"value":{"entity-type":"item","numeric-id":3831058,"id":"Q3831058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$44F83F32-4FEC-4022-AEC8-0CC8DADFF4E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b87f240b74f3f9df9c2b55fdb1be42ca8217e47","datavalue":{"value":{"entity-type":"item","numeric-id":3691772,"id":"Q3691772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$C644DC28-1A1D-4599-A127-ED9B0228ED36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ec4868dba1b37d1adb8bb9f6a23d6c0a862f5","datavalue":{"value":{"entity-type":"item","numeric-id":3880849,"id":"Q3880849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$1D380248-F947-4AE1-9BA3-F4B46BE7BC28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c774834971b086c761bf1be38a21a13366e3f9d","datavalue":{"value":{"entity-type":"item","numeric-id":3758873,"id":"Q3758873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$1AAB862D-8EF0-40BC-91D1-096BD842B977","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26b962d5ada8b5bb3c241cecf1e141991f1d8c34","datavalue":{"value":{"entity-type":"item","numeric-id":918707,"id":"Q918707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$F2333AB0-4782-482D-A0C6-89D36EF1B847","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67b9b8eafd1b87c89b391a5a966c0dde6e01b96f","datavalue":{"value":{"entity-type":"item","numeric-id":1149784,"id":"Q1149784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686245$16DDA09E-1721-4B79-B075-7A87F27FD672","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":"0c401f0036848beb2e3cc435cc223ab28f32b673","datavalue":{"value":{"amount":"+0.8479735255241394","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":"Q686245$123C7BEE-69DB-4FAD-A149-75F537EBE2FA","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":"482d4ad52a56fdf7b2e35ff7442716c1c53c188c","datavalue":{"value":{"amount":"+0.8397244811058044","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":"Q686245$6BE23146-0283-44AE-842C-EFB5EF19A341","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fc4ba812ab474c4478224b01b5cccf4d62fb24a","datavalue":{"value":{"entity-type":"item","numeric-id":3356337,"id":"Q3356337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbdeff8042082a0d0e500a0e6d834fe2fd34bcc3","datavalue":{"value":{"amount":"+0.8233145475387573","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":"Q686245$4CE0A373-4600-405A-8509-3EBB9A0DEECB","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":"bbe417d0a421ad3ccf7249b277ee02bc6036a298","datavalue":{"value":{"amount":"+0.8160769939422607","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":"Q686245$993E0309-9E8A-4460-8366-0F49D30CF0A8","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":"67a0732bb3f13aa0b99b4d8b7fe6241059137b04","datavalue":{"value":{"amount":"+0.8042926788330078","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":"Q686245$0AB5D35F-8CE9-4D11-9A51-91549F4DEC62","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Which claw-free graphs are perfectly orderable?","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Which_claw-free_graphs_are_perfectly_orderable%3F"}}}}}