{"entities":{"Q2366014":{"pageid":2376757,"ns":120,"title":"Item:Q2366014","lastrevid":43949040,"modified":"2025-11-18T11:03:01Z","type":"item","id":"Q2366014","labels":{"en":{"language":"en","value":"Rank inequalities for chordal graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 223109"}},"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":"Q2366014$8BDEA7E3-8CF0-4F91-8F8A-D4FD54EAB028","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b66b35cad6a18bf1f30802ee47d18933e4263342","datavalue":{"value":{"text":"Rank inequalities for chordal graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2366014$D3E9D9A8-7FED-4EB3-847C-D1485647E32A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"914ca8e8e6017c03428e07f2c307364b2973f371","datavalue":{"value":"0774.05055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366014$3285C51A-46C1-4431-933F-0B3E964C21AA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d21daf83aea602c5e8805acc261f2ba5e4cbe9d1","datavalue":{"value":"10.1016/0012-365X(93)90511-Q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366014$4DA281EE-55D9-4028-8014-DB1572AA55F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b16ac91b3719af726a514a0e792e1b6a5d81f1db","datavalue":{"value":{"entity-type":"item","numeric-id":186290,"id":"Q186290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366014$6520E07A-6B83-48A2-9F73-3642B352E4DB","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":"Q2366014$683CECFE-B0CF-4AD4-ACAB-F9186CA313F2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be4381b75afe2df0dbe37cd1a66e006418c0c5aa","datavalue":{"value":{"time":"+1993-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2366014$4CB3493C-776B-417B-9D49-769A134BF6E8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0c272f852e08feca90987d04126485a1f0be7de1","datavalue":{"value":"The (chordal) graphs \\(G\\) discussed in this paper are finite simple graphs such that every cycle \\(C\\) of length at least four has an edge adjoining two nonconsecutive vertices of \\(C\\). The author has introduced a parameter rank \\(G\\) \\((\\text{rk}(G))\\) in order to obtain generalizations of results from interval graphs to chordal graphs. Then he studies relationships between \\(\\text{rk}(G)\\) and the extent \\(e(G)\\) of connected graphs \\(G\\), continuing a previously started program. Here \\(e(G)=1+\\min_ P\\max_ ud(u,P)\\), where \\(P\\) ranges over all paths of the connected graph \\(G\\) and \\(\\text{rk}(G)=\\min_ Te(T)\\), where \\(T\\) ranges over all trees such that the chordal graph \\(G\\) is the intersection graph of a collection of subtrees of the tree \\(T\\). Thus, e.g., in T.3 the author shows that if \\(G\\) is connected chordal, then \\(e(K(G))\\leq\\text{rk}(G)\\) for \\(K(G)\\) the (maximal) clique (intersection) graph of \\(G\\) and in T.7, \\(e(G)\\leq\\text{rk}(G)+1\\) (same hypothesis) (best possible result).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366014$6F2C1181-A156-4BD9-9CA6-61C24CDD4DAB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366014$592BB390-5025-4521-B738-F421B5343306","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9c74856083628862eca49757f3deb6e49bf3b303","datavalue":{"value":"223109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366014$7ED908C5-6D0D-44E8-8E97-282D854E0E99","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6cc52b35d03b83d5162d854c61cf5b039329e","datavalue":{"value":"cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366014$FB34F05D-8D57-4686-9166-EA41692733A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d59ab2c83e0dbd443ebc1f3d0412b712509c0917","datavalue":{"value":"interval graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366014$B8CECEF6-3E27-46E4-8538-5488EEA94CF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"853bd0b31f9734652041500f2e432a6c8df42e70","datavalue":{"value":"chordal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366014$5E3827FF-7B23-4A54-AB28-2A2C43AD3E6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a2fd4ec0406e2038b555fa3ea7e2631f32f4c08","datavalue":{"value":"extent","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366014$9E2CC8FB-2484-410B-B617-4C244C6E6FE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2df313526c4364b4bde459670204713b3745b88e","datavalue":{"value":"connected graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366014$412F42BC-DE2B-47C4-91D6-33C05CAD7F78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e865dcf04feef79efcf163ac054d2ac37b7305b","datavalue":{"value":"paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366014$E277C72C-D177-4B9B-BCA3-8A7E4418EBC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366014$13FE16BF-9370-4DBB-B540-7777C784DC44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bc0d5058cf7773f67ff6548c4fa33edb07db16a","datavalue":{"value":"intersection graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366014$7ACDED52-245A-4DA0-9C2F-255CC41B4610","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366014$37D9FD92-D462-4DCB-930E-F6E42569A896","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":"Q2366014$A3AD5C78-7146-4353-B7A1-73669971530B","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":"Q2366014$64BA6339-6BF3-4FD6-8355-3993F4C49CDD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"82cec48443acb97048e2cdedb86d0d328426b526","datavalue":{"value":{"entity-type":"item","numeric-id":1846437,"id":"Q1846437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366014$4F5DE35E-6D56-45BE-B96B-896B5533CBB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e458531dc8f9b4a4f76ca8cb6a5d9d31ac768ee2","datavalue":{"value":{"entity-type":"item","numeric-id":2562090,"id":"Q2562090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366014$206E14B4-4481-4771-98B8-5B4200FDA54D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c17b1143dff0bc685088f8d62dbc046a1f96e02e","datavalue":{"value":{"entity-type":"item","numeric-id":5732670,"id":"Q5732670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366014$72F5695D-38E8-4A4A-8CF0-63533F7FFE58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efbb5720a2095b9213fc8585d416a45576fcd724","datavalue":{"value":{"entity-type":"item","numeric-id":798677,"id":"Q798677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366014$FCD143EF-C5C0-43F9-AFB2-142E133DE2B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f2f3defb361834302b4cf7d6f481d307ab71a46","datavalue":{"value":{"entity-type":"item","numeric-id":4729802,"id":"Q4729802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366014$865F3595-C89F-46AB-B279-9BF4DA3F496F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b3c6bebedd8e03bc71aea4bd3f45ca4bdc0a3af","datavalue":{"value":{"entity-type":"item","numeric-id":3882481,"id":"Q3882481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366014$233BD777-E1BD-4B62-B9E5-2BC3553BF51E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2ead229aaf202aad2bddaaaf5b2064ab6fc0f171","datavalue":{"value":"https://doi.org/10.1016/0012-365x(93)90511-q","type":"string"},"datatype":"url"},"type":"statement","id":"Q2366014$BC473911-4D22-4928-9725-B4EE8441607A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cfdacbc8b406877a67a2962198767a1c000db675","datavalue":{"value":"W1995085945","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366014$923192A7-780C-48E2-A9DD-9ADB496ED745","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db2fabd8b11715a1ffc9105b59e777b054f21065","datavalue":{"value":{"entity-type":"item","numeric-id":4729802,"id":"Q4729802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25934e9e91d0b53fdd4e6c7c2600dfad11f1aeb1","datavalue":{"value":{"amount":"+0.93804497","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":"Q2366014$94675FC6-C30A-44C6-B481-97FBE7F53D92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efa3bb9a361f6aadd3a7aee5533411169f3ef67c","datavalue":{"value":{"entity-type":"item","numeric-id":2761050,"id":"Q2761050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efb768729ba90a2ae8470599e53255826f92a6b5","datavalue":{"value":{"amount":"+0.9344547","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":"Q2366014$CAC264D3-FD0C-41BE-84FA-FBD6C17B26B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74980009ce0003744ae380ce52ca159e576216f2","datavalue":{"value":{"entity-type":"item","numeric-id":3358760,"id":"Q3358760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c2bc47fafcf0ea4b97eb9c5356feab38dd09ff3","datavalue":{"value":{"amount":"+0.93265605","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":"Q2366014$F0A92FA5-F950-4F47-9E19-38C4EC259F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c880179c2bf710458a5d56e0d87119512bb8963e","datavalue":{"value":{"entity-type":"item","numeric-id":844166,"id":"Q844166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e326e8f6da1f43ced1ae134400543831e05ddaf","datavalue":{"value":{"amount":"+0.8965727","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":"Q2366014$B30DA5F4-6F5B-4BBE-981E-0ACD0FA268DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ca7f2ee9a983c521d4907499b9cd70aceed8b74","datavalue":{"value":{"entity-type":"item","numeric-id":3328563,"id":"Q3328563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6de2b335f01526a0540b72fdcb3e1b8a5df3c8c1","datavalue":{"value":{"amount":"+0.88684416","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":"Q2366014$DF917B20-0B13-4385-8DAC-7C6B8387B615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59ff62a63929e4c6b8d4c7bf058f39d9880db8c5","datavalue":{"value":{"entity-type":"item","numeric-id":4693359,"id":"Q4693359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b29a269eb028827a6678dd7443ed01803b9ccaf","datavalue":{"value":{"amount":"+0.884983","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":"Q2366014$5802BC3F-03F3-4684-956D-ED4843B1109D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b7862ba32774a8e0ce4b5c77abb125a079237d3","datavalue":{"value":{"entity-type":"item","numeric-id":868005,"id":"Q868005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62287b9a079cdaed39b7344d6e7ed97e11e96bf9","datavalue":{"value":{"amount":"+0.8837051","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":"Q2366014$BA4FD0FF-A7DA-49B9-9E99-1F4238449ED3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0a654ca565dde7ad4c5332b81ce25d1c9340fa6","datavalue":{"value":{"entity-type":"item","numeric-id":2856696,"id":"Q2856696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a348c0ad97aa6d70c7c9b8d5bfa1a33fda5739d","datavalue":{"value":{"amount":"+0.8822491","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":"Q2366014$609A5B3E-48CC-47D2-9E5E-44E6AE7737BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e11c7e7c50d39fce6863570093fb255e086b2020","datavalue":{"value":{"entity-type":"item","numeric-id":389640,"id":"Q389640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be4a593934b47fa5342464bf940f4bfded2c2f1d","datavalue":{"value":{"amount":"+0.8808796","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":"Q2366014$9C22D21E-2FB3-43DD-ADF1-7D7A2BA63B0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee4d496f2aa983567744f5b9bb3353060699e7a1","datavalue":{"value":{"entity-type":"item","numeric-id":2462396,"id":"Q2462396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee5855c1e4a5c928c61737435df71bb9c633d6d0","datavalue":{"value":{"amount":"+0.8799499","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":"Q2366014$EBE5DADE-C6F9-4D28-8C42-23ADA861021B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2366014","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2366014"}}}}}