{"entities":{"Q792348":{"pageid":794196,"ns":120,"title":"Item:Q792348","lastrevid":64375029,"modified":"2026-04-11T19:26:26Z","type":"item","id":"Q792348","labels":{"en":{"language":"en","value":"The edge intersection graphs of paths in a tree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3853141"}},"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":"Q792348$86BC876A-AF8A-43FA-A471-EF2BCC1C97BF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5e8c949b14960320df27fe6a7f9c621d5e9ca84d","datavalue":{"value":{"text":"The edge intersection graphs of paths in a tree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q792348$C1AF4880-9D22-4379-94FD-CBA1417353DF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ab82b5a63d0f04c6bbb937b74e022a91785add51","datavalue":{"value":"0537.05063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792348$DC6F5BEF-06A2-482E-9ED6-44EE7699D525","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c7963fa17e56c9beb896a15b8150838b55373871","datavalue":{"value":"10.1016/0095-8956(85)90088-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792348$C6816A31-4DF2-4162-B7FE-94E036F8BF4A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b8eeeb529fb23a3ef59896edd03b07a25ad48fec","datavalue":{"value":{"entity-type":"item","numeric-id":251894,"id":"Q251894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$E1F4B69E-B713-410A-92BC-25A9E2CF11AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b5568209d45f3a5ad30fd32c4628508c6203ed9a","datavalue":{"value":{"entity-type":"item","numeric-id":221641,"id":"Q221641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$3F5FC7BA-5D44-4869-8C74-DB7807832DE4","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":"Q792348$B08F06E2-643D-4006-AEF6-D92DCDF531E5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q792348$59F841CB-FB3F-4A19-8451-C4C0554F0F9B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e1e33df5f832ac32e9d771b1ee5b86383b907b46","datavalue":{"value":"We investigate the class of edge intersection graphs of a collection of paths in a tree (EPT graphs) where two paths edge intersect if they share an edge. The cliques of an EPT graph are characterized and shown to have strong Helly number 4. From this we demonstrate that one can find a maximum clique of an EPT graph in polynomial time. We show that the strong perfect graph conjecture holds for EPT graphs. Further complexity results follow from the observation that every line graph is an EPT graph. The class of EPT graphs is equivalent to the class of fundamental cycle graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q792348$DFCD4C1E-FE60-48DE-AC73-AB855A92F8B3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792348$37C99F6F-7149-4A37-AA6B-B2FA58D6ECB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792348$0BBCE91F-58DA-4280-ABF3-FC57D43DE936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792348$B0ECAAF8-4624-4897-902E-7F67845A30AD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1b1586e1037795cb2b5cd0d0f085394edc68be67","datavalue":{"value":"3853141","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792348$E3CF283F-613B-4BD2-AAD1-A47365E46C2D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c7c0d9a4f0eda9ce631cac2cdcfb1eb34a0511a","datavalue":{"value":"edge intersection graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q792348$E82E0B9E-6729-484E-82F7-3714F48A6B9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a153084f07a75cc56b26c617236589c3c4eb947","datavalue":{"value":"cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q792348$881CD233-F72D-432E-942E-8CD2DAAD3134","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"131d7ca85fac180adee1394dee19fee7e96446a0","datavalue":{"value":"strong Helly number","type":"string"},"datatype":"string"},"type":"statement","id":"Q792348$13CBE344-0FB1-4DE3-96C7-9A4BB271A29C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a11116a6b4821127d46d686f666f969b50e0a4e","datavalue":{"value":"strong perfect graph conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q792348$2778C0C2-E625-4C30-A18E-B24E95CD1983","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":"Q792348$380B14F0-2BF6-46A4-ADF3-A13D64402186","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7e60b2a962587d025d2dbc9eb375fb4e9b9b135a","datavalue":{"value":"https://doi.org/10.1016/0095-8956(85)90088-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q792348$FD7D0B01-3B68-4449-8101-A18C354BF8E2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8c111e104b00ab5cd54effff25e058d32afa9c21","datavalue":{"value":"W2017793597","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792348$AFB10775-8FDB-4100-9110-5713BF8D26A7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"710b3812b6cc583a4ac50892971157a70addcd8e","datavalue":{"value":{"entity-type":"item","numeric-id":3671194,"id":"Q3671194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$5FEE0656-F7EE-423D-B4E8-527393883C77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$BBC59555-8803-44B6-9FE1-5D96D1B69A94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"806d9ffa7632415b7be5efb8329eedf631c75c21","datavalue":{"value":{"entity-type":"item","numeric-id":3688409,"id":"Q3688409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$7A7A3D8D-5DDB-4111-9714-5BE9DC1DEE66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db17c37245dbe94f0a7b083679e1c3fed2c818d1","datavalue":{"value":{"entity-type":"item","numeric-id":1837210,"id":"Q1837210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$57896029-8C47-4469-9FE1-6B525C6652FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83ab81b85457f990d5674daf61fc32a97eb26853","datavalue":{"value":{"entity-type":"item","numeric-id":1254334,"id":"Q1254334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$BDC83513-AC0B-48A4-8D15-8B5D2AA20F2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2362ed226b34fd21fa5e856182cb167fecc51e3","datavalue":{"value":{"entity-type":"item","numeric-id":3218158,"id":"Q3218158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$68ECB1B6-3A46-4618-9D6A-683441CF19C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$6753921E-1236-4570-95E1-3E9CA13075B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2e498f8f059ec2cdc0575cdc006d5c453bc3e3f","datavalue":{"value":{"entity-type":"item","numeric-id":1060226,"id":"Q1060226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$8404452A-C878-444A-B3E7-2326ED437D7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ef58403004f3e1d4153f584ad51355fa1f0b6b9","datavalue":{"value":{"entity-type":"item","numeric-id":1159682,"id":"Q1159682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$1192CBA6-4866-4B2B-9B1D-B8F2408CAC5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"539aaf1c2016b72fbd780a24314c54b8ca10d3f5","datavalue":{"value":{"entity-type":"item","numeric-id":1162705,"id":"Q1162705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$D9B2E83D-1525-41A2-AE20-306E1115CB11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"504295ab6ede06f72a77125fc9a02f368947b8a5","datavalue":{"value":{"entity-type":"item","numeric-id":3940405,"id":"Q3940405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$15AB2DA8-1ACC-4652-99C3-736C7AF37711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af8893a76a836311843664e425c713b5ed4de57c","datavalue":{"value":{"entity-type":"item","numeric-id":3956975,"id":"Q3956975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$C323AA26-3164-4730-9094-5B32E709D587","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ae082348485f041e5a3df3046ab38c5996135be","datavalue":{"value":{"entity-type":"item","numeric-id":1235990,"id":"Q1235990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$701E7686-CC0B-41D0-9CE2-D8CB50375C95","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":"Q792348$5FD36A8D-A549-4445-BA47-9F6360948D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f2ea9e473a8cf61f64728aa7c6cf40b378a168a","datavalue":{"value":{"entity-type":"item","numeric-id":754232,"id":"Q754232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$13B7BF4E-EB86-4C98-AA81-F698E8BF5D5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b775f326c39465f64d984d6ba0226a1da49dc8aa","datavalue":{"value":{"entity-type":"item","numeric-id":2538093,"id":"Q2538093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$251C6083-CDCF-402F-AD7C-09C93C7CE796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4d06e8ffe51c0e0e5032701b55a85074de5383c","datavalue":{"value":{"entity-type":"item","numeric-id":5790769,"id":"Q5790769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$ACEE58AF-E058-45E4-88C2-185B503585CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe54b2ecd912ed25c63e5f7b4a878d45237c4726","datavalue":{"value":{"entity-type":"item","numeric-id":4200254,"id":"Q4200254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$6F1CA44B-0D6B-4AC9-8874-4C6D488D3DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24b8dc6f087c17b1a2b9522e8477786984785e52","datavalue":{"value":{"entity-type":"item","numeric-id":1160186,"id":"Q1160186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$802DF9AB-E04D-426A-89BB-E34945C9F728","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39c83322ec89a0879c019f012ce18dfec20bc796","datavalue":{"value":{"entity-type":"item","numeric-id":1062072,"id":"Q1062072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$727FFC4E-CF79-4AA3-B117-B74DF03237D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a234d40c983ecb7ddc69f083b260c6a081b496a","datavalue":{"value":{"entity-type":"item","numeric-id":4141848,"id":"Q4141848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$89F604A8-AEDE-4595-A6FC-1124148D986C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cceb1234cc3145b85555d80daa70c1ec324e91e6","datavalue":{"value":{"entity-type":"item","numeric-id":5663885,"id":"Q5663885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$C618DBFF-42FA-4AE6-8A30-58AB69D151EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1b5d4123720dba00bb1bed097939282270f6524","datavalue":{"value":{"entity-type":"item","numeric-id":4071258,"id":"Q4071258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792348$1695B938-A7F1-4CB9-A0C4-3DA71614FB9F","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":"Q792348$EB7B56DD-7B57-4526-A303-8E5712504BCF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5df9425d5d8dd94191054ad1165c4ae05d092881","datavalue":{"value":{"entity-type":"item","numeric-id":1060226,"id":"Q1060226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1983bfb8ce31880069d01ffdbd9a6be023e9cf76","datavalue":{"value":{"amount":"+0.9019142389297484","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":"Q792348$EC90568C-AE79-4439-84B2-8B51CDE2230C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"419512ea8805affe4a024c7231ba8698ca0587e3","datavalue":{"value":{"entity-type":"item","numeric-id":1038105,"id":"Q1038105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91732194aaac0a8cdffe907349f9e5f9bfe897e6","datavalue":{"value":{"amount":"+0.8787922263145447","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":"Q792348$EAF0B1FE-886D-42F0-94ED-388B20E10B20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f26c3aa26f3c706a25995fe09c00ccffd5d12d56","datavalue":{"value":{"entity-type":"item","numeric-id":1061147,"id":"Q1061147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ee68375dce83244003aa4eab60bde91d77e620f","datavalue":{"value":{"amount":"+0.8648496270179749","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":"Q792348$25F5F54F-DB5A-4E90-B4A2-A13EA88CE1A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52bb288b0bfc12962e345f3f246775adacf90e70","datavalue":{"value":{"entity-type":"item","numeric-id":3576666,"id":"Q3576666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff44754cafaba88d5fd278a8885ac3a341b3265d","datavalue":{"value":{"amount":"+0.8564226031303406","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":"Q792348$98AF0AE6-049C-4FA9-81AE-F0F92D9D6A7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd7fdd0b4c7e1efc1904ee60f61598ecfec31bcf","datavalue":{"value":{"entity-type":"item","numeric-id":2473042,"id":"Q2473042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ce789bfd35382e4ea7030c17c1c017ad01da93b","datavalue":{"value":{"amount":"+0.8522006869316101","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":"Q792348$01CED59B-479A-4DAC-B383-1D4A1157A577","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The edge intersection graphs of paths in a tree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_edge_intersection_graphs_of_paths_in_a_tree"}}}}}