{"entities":{"Q1613508":{"pageid":1624248,"ns":120,"title":"Item:Q1613508","lastrevid":72343347,"modified":"2026-04-14T04:15:56Z","type":"item","id":"Q1613508","labels":{"en":{"language":"en","value":"Three forbidden subgraphs for line graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1792434"}},"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":"Q1613508$EA1424F0-C87C-405D-B6DB-599D1CF551B8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8806d4bd07c353894e6a9126979ca6f439bc6d8c","datavalue":{"value":{"text":"Three forbidden subgraphs for line graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1613508$C3451796-5149-4169-B740-122E824647D8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"100cea1f3ccfe1a6c0d77f4d2d52e6c2023bb6bf","datavalue":{"value":"1003.05092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613508$9BB3C5AC-60C9-497D-A8D2-E5146F224285","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6489c6d8e9ffdb6bb006b0c08b5d0a14bc0ff0d1","datavalue":{"value":"10.1016/S0012-365X(01)00459-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613508$5EE8568E-B504-480F-ACD9-6BD218389FC5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"26182120854703deb6ac89dfb33caad39aee4c88","datavalue":{"value":{"entity-type":"item","numeric-id":479057,"id":"Q479057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613508$76AE16E7-6EB6-4C68-8F88-7F02FAA5A0F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1cc83fa69e59b2432e007c806af144789f7a8470","datavalue":{"value":{"entity-type":"item","numeric-id":342189,"id":"Q342189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613508$05BE4F23-5357-4304-869E-0BD5F46CCBE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fae95af870128491d4338ab3676d2db43143a781","datavalue":{"value":{"entity-type":"item","numeric-id":898051,"id":"Q898051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613508$F2335B0E-A815-4885-AD60-38D25922FCAB","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":"Q1613508$79050A77-611A-4F5D-B31A-39CE5DB81DA7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"04ef60e6a08d63a03521c7b80b58e0a998b63b55","datavalue":{"value":{"time":"+2002-08-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":"Q1613508$156E3C2F-9994-45A6-9490-3B1E9568514A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0e32df6d14d58f2d0acc9d2a3e5938ca7f8900a0","datavalue":{"value":"Beineke has shown that a connected graph \\(G\\) is a line graph iff it does not contain any of nine graphs drawn in a figure as an induced subgraph. This result was improved by \u0160olt\u00e9s: \\(G\\) is a line graph if it does not contain any of the first seven graphs given by Beineke as an induced subgraph and is not isomorphic to any of five additional drawn graphs.   The present authors construct three graphs with the property that a 3-connected graph with minimum degree at least 7 is a line graph iff it does not contain any of the three graphs as an induced subgraph (Theorem 3). This statement is proved by disproving a conjecture of \u0160olt\u00e9s which he had concluded from his above-mentioned result. The present authors also show that the number of excluded subgraphs cannot be reduced, no matter that connectivity is specified.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613508$63F6E147-A1FB-43FD-B989-4D84427230AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613508$65BBD7AD-4C45-46EC-BFED-1A6AEEC61D9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613508$033653EA-9857-4D11-88E5-CEC6F88E14A5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8c4c9843de41677faa8aaef533fb2e55deb655c3","datavalue":{"value":"1792434","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613508$D3967453-832D-4FBF-BB8E-AE73C2D75216","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34783be7cb07be74f453b9d5a8761bddb5dcf0b1","datavalue":{"value":"line graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613508$21BBE008-8A42-42D8-B297-BF846177F0AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1db4e3cd8c6237e3b25098b483a3ff821c3b321","datavalue":{"value":"forbidden subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613508$FC32F35D-27B7-449A-9BD7-CF2FF3774EA8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31cef456e8646accdc28b523a232a52220366047","datavalue":{"value":{"entity-type":"item","numeric-id":593309,"id":"Q593309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613508$6DAECC1B-DB59-4EEC-AEF6-BE97673B28DA","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":"Q1613508$CFF5F74D-F459-4145-8EB0-96D9063211BB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"31ac351288953e40ef911ea6fe4c3d765a45ac8c","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(01)00459-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1613508$18F05B80-DB69-45BB-9F55-5F14BBBE445B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eeb732a6fd4b0780ec13814db4c2c28b2e6f1d2f","datavalue":{"value":"W1990219340","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613508$D68EE718-3DA8-4252-BD97-E5425497C8AE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"953d418994321f1815607022ed0311deff46fcbd","datavalue":{"value":{"entity-type":"item","numeric-id":1336680,"id":"Q1336680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14239899acbbc2a10969eb4c5f1d3807e6c26710","datavalue":{"value":{"amount":"+0.91958666","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":"Q1613508$0D2DFC14-FCD1-48F8-BB36-C0D5DC4D5C09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97030bce6eb4498e1096100c29c3573d6b6cac3a","datavalue":{"value":{"entity-type":"item","numeric-id":1850532,"id":"Q1850532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5819e44b52f82ff8a6b8cadcd019ddcd5ff4a442","datavalue":{"value":{"amount":"+0.91790926","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":"Q1613508$A175660C-F90E-40F9-989D-E9C442093D98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4036a6c4bd476a2f0799e2631bb03b2979b76b81","datavalue":{"value":{"entity-type":"item","numeric-id":1314883,"id":"Q1314883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5faa6639fee4f6b9039979b9fc9ac8e79f2d0d9","datavalue":{"value":{"amount":"+0.91099864","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":"Q1613508$DFED4BDB-8208-40D9-BDB4-7F2684C1CE53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"563fd57637ceda418a4c67823668b2519aac0e87","datavalue":{"value":{"entity-type":"item","numeric-id":2935268,"id":"Q2935268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f0e167cc29041dfd563f307d436c629bca1a879","datavalue":{"value":{"amount":"+0.8933967","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":"Q1613508$3DA2D58C-D861-4A32-910A-5982436D0674","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14c375e5278c66bf0118a18f28bd863a5db50ace","datavalue":{"value":{"entity-type":"item","numeric-id":5855535,"id":"Q5855535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46a802457a1b07bb6e3eb6a8481b4e02c4669812","datavalue":{"value":{"amount":"+0.8806287","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":"Q1613508$2D24A20F-1575-456C-8120-C963BAC3D7A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d665179aca0d5e4e400fedc380bed9c379185849","datavalue":{"value":{"entity-type":"item","numeric-id":3838229,"id":"Q3838229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73e4be7b31118786cc36de16944edeb57d6c7992","datavalue":{"value":{"amount":"+0.8758122","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":"Q1613508$828D9C2F-6635-4178-957E-45AC7FDEE195","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ed2bb13a92a978f3ee07430b85b0ec6ac0c0535","datavalue":{"value":{"entity-type":"item","numeric-id":2816134,"id":"Q2816134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eaf272fddb85084b479a12210eb6e6f91561f911","datavalue":{"value":{"amount":"+0.8737868","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":"Q1613508$F14C515F-BA83-4133-9909-138CA3821D39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de1b45d903c2d70f27164e839c1ce7a376fcda63","datavalue":{"value":{"entity-type":"item","numeric-id":4575707,"id":"Q4575707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fd381ee264c0ef27c1248256ed2cc88e65203e8","datavalue":{"value":{"amount":"+0.87145203","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":"Q1613508$F99E9FD8-7331-4A02-A6AF-28067700CFA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcf4c40bf43bcd252a302695040323c4ae2c4873","datavalue":{"value":{"entity-type":"item","numeric-id":4213895,"id":"Q4213895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"268d17a5fba379aea95751ab5982e4897fad268c","datavalue":{"value":{"amount":"+0.8711779","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":"Q1613508$115127E5-DC3E-4022-AA6B-67A91522BD8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37b219c41e51bb7f71bc75eac98bf8e8446a0922","datavalue":{"value":{"entity-type":"item","numeric-id":287897,"id":"Q287897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c905f275ca8adc8ee6172b636b46b3e3ea25e29","datavalue":{"value":{"amount":"+0.8706666","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":"Q1613508$0D96814E-7778-4B73-9159-52CBF96D6493","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Three forbidden subgraphs for line graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Three_forbidden_subgraphs_for_line_graphs"}}}}}