{"entities":{"Q1766108":{"pageid":1776850,"ns":120,"title":"Item:Q1766108","lastrevid":72485016,"modified":"2026-04-14T05:14:28Z","type":"item","id":"Q1766108","labels":{"en":{"language":"en","value":"Graphs with least eigenvalue \\(-2\\): a new proof of the 31 forbidden subgraphs theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2139255"}},"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":"Q1766108$D7AC7F89-B58E-4173-871A-FB9DF5DC4FC1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4034e11b7d819051bd7e78ada40a76294f7f4132","datavalue":{"value":{"text":"Graphs with least eigenvalue \\(-2\\): a new proof of the 31 forbidden subgraphs theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1766108$AF3CA97C-9EB9-40FC-A537-7EE714435132","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0867853aa1d500e459e708d66fa6aeb122170f2f","datavalue":{"value":"1063.05090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1766108$3845E9F0-17C5-4FB2-92AB-07A752DDE8DB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3db7d4aede42575ee9ca1b3081433ec8fcd4840a","datavalue":{"value":{"entity-type":"item","numeric-id":385376,"id":"Q385376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$D720AB1E-A6C6-4EE8-A25C-B0843D1E9CEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ee130c9b7f60a5b1364d597046dcd0740de6d4e3","datavalue":{"value":{"entity-type":"item","numeric-id":1299997,"id":"Q1299997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$C7F305C6-E7FB-42DB-9D31-5B3497B1CF15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9451c4cebeea531e5de3a4edf6d17edf71b2027","datavalue":{"value":{"entity-type":"item","numeric-id":1220947,"id":"Q1220947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$D223FBB4-72E8-4402-A2ED-8404440BD4DA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fb34abbf39f11094509111953e4c62a22b1e3897","datavalue":{"value":{"entity-type":"item","numeric-id":115940,"id":"Q115940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$2441BF36-59A6-43AA-B352-7F77BEDDBEBE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d5dabce90ff5340c0b0fd5844437bb5a756de645","datavalue":{"value":{"time":"+2005-02-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1766108$1E3E4994-300C-4E47-B318-29DD0A6F3F0D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e7057d53900a882961122b36706e95674055920d","datavalue":{"value":"An early observation that line graphs have least eigenvalue greater than or equal to \\(-2\\) led to the natural problem to characterize the graphs with this property. Such graphs turned out to be generalized line graphs and a few hundreds of exceptional graphs [see \\textit{P. J. Cameron, J. M. Goethals, J. J. Seidel} and \\textit{E. E. Shult}, J. Algebra 43, 305--327 (1976; Zbl 0337.05142)].  Generalized line graphs were later characterized by a collection of 31 forbidden induced subgraphs in [\\textit{D. Cvetkovi\u0107, M. Doob} and \\textit{S. Simi\u0107}, J. Graph Theory 5, 385-399 (1981; Zbl 0475.05061)], and independently by \\textit{S. B. Rao} et al. [Proc. Symp., Calcutta 1980, Lect. Notes Math. 885, 459--472 (1981; Zbl 0494.05053)].  However, the existing proofs of this result are rather involved. The paper under review provides a new proof by introducing an edge-colouring technique for investigating minimal non-generalized line graphs. It is then shown that such a graph has at most 8 vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1766108$5F8FBB34-1C75-4747-BBB1-3B3C3A30D627","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"94626be276206b45b57e94a7e29516fb1870dd91","datavalue":{"value":{"entity-type":"item","numeric-id":190550,"id":"Q190550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$00CA57FB-E317-40D3-B964-663AD6186D5D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1766108$95CB0C01-609A-4B1D-ABBA-A8981A40B9E3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a05a86001a01c70ebc2460304c6076876b244bf3","datavalue":{"value":"2139255","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1766108$34D19C13-E769-4F90-B01F-0E62C742E031","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c09ff776616565c6abfca73ec4964ec53fa2b3a3","datavalue":{"value":"graph spectrum","type":"string"},"datatype":"string"},"type":"statement","id":"Q1766108$5A5F292C-C8C3-452F-8C59-AB49BB2535EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80f9e19f12a52866948bd428a7ca259da6f85374","datavalue":{"value":"generalized line graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1766108$FB8ECBA6-3CE5-443D-A104-7D3503D74452","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":"Q1766108$E89FF9CE-54C5-487C-9B6C-209C802C5040","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f9edc2c83be11af5929965ab2a3aeb0a1ffd6e04","datavalue":{"value":"https://doi.org/10.1007/s10623-004-4856-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1766108$1D8B3231-1A08-4703-AF85-46331F2803AB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f9039b81bc067a2536f72f85e4828e692857f75e","datavalue":{"value":"W1998386707","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1766108$759A2A6B-CF32-4F47-A0FB-E7D8C5CB3DA3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f63e38e4851ca0e3a13042d4f415c0b9fe4f5434","datavalue":{"value":{"entity-type":"item","numeric-id":5601346,"id":"Q5601346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$0B09F569-B62A-4B88-9BAB-BCA80B33D802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13194cf893f489d0865faa2f8e943a5202fac2a8","datavalue":{"value":{"entity-type":"item","numeric-id":1229893,"id":"Q1229893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$0A6CCE32-09DD-44E7-A996-A30C9EF1911E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b23e7bc5a087cd8dcbc80276e5103647248fb256","datavalue":{"value":{"entity-type":"item","numeric-id":4000288,"id":"Q4000288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$E4F3CFA7-C5C3-4F29-BBA2-DCB1A2BDEBC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbdf2406eb1ffb1ca08e129cec303daaf9a1e818","datavalue":{"value":{"entity-type":"item","numeric-id":1855399,"id":"Q1855399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$7BE2AE6C-8C26-4F61-ACAD-CBDC7D7A0188","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1d15e07f32200f40625ba7dc38326f04c1869da","datavalue":{"value":{"entity-type":"item","numeric-id":3931435,"id":"Q3931435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$B7CC068C-B630-4B4E-B823-9BC28A327435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfd7785cb777022b40fc2c2e76062cd46b78ef4e","datavalue":{"value":{"entity-type":"item","numeric-id":789413,"id":"Q789413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$4936C2B1-4116-4421-9D3B-C874A79C5E38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10695a43368b4e56633bb7eff1abc6f3c936aeb4","datavalue":{"value":{"entity-type":"item","numeric-id":5949011,"id":"Q5949011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$2C2A45A9-D231-4DAD-9B7D-4256687A0D73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"250068d58befb1ddde4fdb173dc3bab29b389968","datavalue":{"value":{"entity-type":"item","numeric-id":754883,"id":"Q754883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$D4430E0A-657C-41A6-8012-7FFA432FF592","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f42ea7154ee6cde21cf93adf9cda8c492c29308","datavalue":{"value":{"entity-type":"item","numeric-id":1168987,"id":"Q1168987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766108$84C9C273-1875-4A6F-A81B-AF3D4C0FED6F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a4e22ff82c3c7928fad60913471c5012d9a5c9b3","datavalue":{"value":"10.1007/S10623-004-4856-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1766108$DD232FFF-AE60-4B02-9085-08757489D50E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0790194b9e763813db863d15157352b998beef90","datavalue":{"value":{"entity-type":"item","numeric-id":4828550,"id":"Q4828550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43d3a101fa22210639d1d24d24a92a538c9430c5","datavalue":{"value":{"amount":"+0.8281108736991882","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":"Q1766108$7931B274-DA62-41A0-814A-6C22EE5A8F5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cf37ded117fe322cd1138e30f0633a957cf8ab2","datavalue":{"value":{"entity-type":"item","numeric-id":3765811,"id":"Q3765811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee258a5190aa4665f9ad59dfffa30a968cd3ddf4","datavalue":{"value":{"amount":"+0.8219953775405884","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":"Q1766108$9CDE3024-B765-4745-9897-2708D9DD216C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e00605543fe1db8b24c4dfb9842b41d6cd32e16","datavalue":{"value":{"entity-type":"item","numeric-id":4906174,"id":"Q4906174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6426002b8ef190cc884cba7467c996427343341c","datavalue":{"value":{"amount":"+0.81413733959198","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":"Q1766108$D12B72C3-56C3-4AC3-A39D-B801B974D064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4f918f0cd4f3ecfc7e7a5e4909106d65ec6aa00","datavalue":{"value":{"entity-type":"item","numeric-id":3535845,"id":"Q3535845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3221f3138e6027e3b425130ac6e6592d2419d7d9","datavalue":{"value":{"amount":"+0.8119592070579529","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":"Q1766108$1E6F567B-CBDB-480C-AD66-DDD7976ECF83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ceeb0d9adc07e80747f3553d759351e026b9867","datavalue":{"value":{"entity-type":"item","numeric-id":3340892,"id":"Q3340892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"597633c53d5f13a7e9e8d1b6620f391b2bf53443","datavalue":{"value":{"amount":"+0.8110854029655457","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":"Q1766108$FFAD1256-406C-4C42-B7C9-519B6D42F96C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graphs with least eigenvalue \\(-2\\): a new proof of the 31 forbidden subgraphs theorem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graphs_with_least_eigenvalue_%5C(-2%5C):_a_new_proof_of_the_31_forbidden_subgraphs_theorem"}}}}}