{"entities":{"Q5946757":{"pageid":8123559,"ns":120,"title":"Item:Q5946757","lastrevid":47688097,"modified":"2026-01-02T10:45:12Z","type":"item","id":"Q5946757","labels":{"en":{"language":"en","value":"On the recognition of \\(P_4\\)-indifferent graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1659504"}},"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":"Q5946757$8A97F2D9-7736-432B-A168-092D40E6E433","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b13a67b89869663464cf9c790005658af27c9e69","datavalue":{"value":{"text":"On the recognition of \\(P_4\\)-indifferent graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5946757$EBC075AF-D86D-41A4-95BE-963E4425DE06","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c02d9c4afb251247333dedae4fddd490e22fc1dc","datavalue":{"value":"0979.05096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946757$8BAEF6C3-4191-466D-98B6-D14ABFF80DD0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"931f44004ac79f870e1deb69a3addd5ccc86a10e","datavalue":{"value":"10.1016/S0012-365X(01)00050-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946757$0C388EB3-285A-4A6D-AB24-2ECCAD21F401","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"186bb8da4d9a21e884eff28e3a0bd8547b44ac9e","datavalue":{"value":{"entity-type":"item","numeric-id":168651,"id":"Q168651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946757$4A633064-CF79-4667-AF4C-261DB29BACF6","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":"Q5946757$3A27D833-40C8-4DE5-9EB1-A10714CFE681","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63e1d7063ecd638677848b844accef77290c7ea4","datavalue":{"value":{"time":"+2002-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5946757$CD68ABB4-EDD6-45CA-8D34-820A055F4A1E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"69c8c4821fd8aad4a298b7363c82cbfffb056264","datavalue":{"value":"A simple graph \\(G=(V,E)\\) is \\(P_4\\)-indifferent if it admits a total order \\(<\\) on \\(V\\) such that \\(a<b<c<d\\) or \\(d<c<b<a\\) holds for every chordless path in \\(G\\) with vertices \\(a,b,c,d\\) and edges \\(ab,bc,cd\\). The class of \\(P_4\\)-indifference graphs sandwiches between the subclass of proper interval graphs and the superclass of perfectly orderable graphs. \\textit{C. T. Ho\u00e0ng, F. Maffray} and \\textit{M. Noy} [J. Graph Theory 31, No. 3, 155-162 (1999; Zbl 0929.05073)] characterised \\(P_4\\)-indifference graphs by forbidden induced subgraphs. The paper outlines a linear time algorithm for recognising \\(P_4\\)-indifference graphs and computing the corresponding vertex orders. Another such algorithm was forged by \\textit{M. Habib, C. Paul} and \\textit{L. Viennot} [Discrete Math. Theor. Comput. Sci. 4, No. 2, 173-178 (2001)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946757$D4FE0363-068A-4487-9B40-4F7F0DEA8F4B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946757$B782554F-7813-422F-9686-1A498295D75F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946757$C38F0A80-575F-4E44-A683-29EF5ECA3E65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946757$9E85A1AA-8E5E-4BF9-AEB4-C54792E96906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946757$7AE5708E-26F1-4E7A-B176-A9FC41650EDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946757$AB69F44E-62AA-4902-A738-BB1B5837193B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946757$FD5B220B-DA32-4B95-AC61-1BC7C1CCF455","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9126e601557d1e4f03e1d56c1b8b4d3482226a04","datavalue":{"value":"1659504","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946757$9687F845-76A4-4696-B666-AEC7803E3236","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a38b11968d7cb86be0842b661cd5bdd713115f5","datavalue":{"value":"graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946757$42534F96-A489-493B-ADD4-7946292A07E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"286c7ea134b548c331c7c24b617979de9c7c683e","datavalue":{"value":"\\(P_4\\)-indifference","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946757$334E54D4-8EFF-47CB-B520-C5F384FE845A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da6c78b67096b558b6a5b7f77cad8eea1fc65662","datavalue":{"value":"linear time","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946757$51AF252E-82BA-4BE9-B252-0422C36713BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9891227b3d7ca9f091fdc17473271d45c5e2f962","datavalue":{"value":"recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946757$1D910DA8-083F-4E19-A416-08E364943605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1adb1579ecb6bb9aaca40d9ceb17f3584d731fa","datavalue":{"value":"modular decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946757$FEB61DFB-B656-4284-B5CF-B6B57E6407D1","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":"Q5946757$369BE9E9-4E59-4C61-BC3A-3436C72DD7E3","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"fbcc3a53c46b2a3e4e2ab3cd9ebf1635a678d1bc","datavalue":{"value":"Q127719011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946757$F7C089A6-03B5-4831-AB1C-D0E655391B21","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40e6c65477b050bbe1ca7b74fa1fec0a841736e7","datavalue":{"value":{"entity-type":"item","numeric-id":2752464,"id":"Q2752464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c37c3c403320dba253a536b5a156ce6181068c3","datavalue":{"value":{"amount":"+0.9254443049430848","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":"Q5946757$3731F5FE-0DE6-4D11-BD9E-CF63CFB4E543","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a520d454e8a2d930da4ca167f0f64e54ab1be53f","datavalue":{"value":{"entity-type":"item","numeric-id":4256088,"id":"Q4256088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3823478426a80542902372fa38452b7ba0831668","datavalue":{"value":{"amount":"+0.8920502066612244","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":"Q5946757$C7DACD87-5A68-42CC-BA21-0DAD4727055C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b692ef71d3a07f74c574a8f2d208e421935c73ed","datavalue":{"value":{"entity-type":"item","numeric-id":1121924,"id":"Q1121924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4203140d73de3743d73c3db57381f4b7daf05fca","datavalue":{"value":{"amount":"+0.7759491801261902","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":"Q5946757$DA9ABC5F-816C-4C23-B693-5B1F4615C521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f07023917195aa7becc1d79db37341d9ee8c2c11","datavalue":{"value":{"entity-type":"item","numeric-id":1971221,"id":"Q1971221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ab3e47e7300f7ff8907cfd7ee37e9bd5e443081","datavalue":{"value":{"amount":"+0.7680892944335938","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":"Q5946757$3BA6F6D5-9B93-4EF4-840A-218BCFEE2C87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b09f969d7a47514076abf123d45394241cdb38c","datavalue":{"value":{"entity-type":"item","numeric-id":3355252,"id":"Q3355252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ab3e47e7300f7ff8907cfd7ee37e9bd5e443081","datavalue":{"value":{"amount":"+0.7680892944335938","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":"Q5946757$9E3EA5D2-6CD7-42CD-9DF4-E35F72226F50","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5946757","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5946757"}}}}}