{"entities":{"Q631642":{"pageid":633490,"ns":120,"title":"Item:Q631642","lastrevid":51207092,"modified":"2026-01-17T06:04:40Z","type":"item","id":"Q631642","labels":{"en":{"language":"en","value":"The fine structure of octahedron-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5865467"}},"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":"Q631642$830B1091-A59C-40C6-8BF8-006D02A8F2B1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8f893224a14719be2e3c449d5b627ba6876f53e4","datavalue":{"value":{"text":"The fine structure of octahedron-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q631642$89F6771C-7C85-415F-A05E-985EAEE05317","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9c8d1504b723c454a5dfbb203dea3d68198dfd07","datavalue":{"value":"1239.05098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631642$9833666C-7049-4DBA-BD27-2D9CD29DC194","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9158385d8dfa25fd1cbf34c726849285f5355cf","datavalue":{"value":{"entity-type":"item","numeric-id":189372,"id":"Q189372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$7DFE286E-FF1C-4479-9479-C0A14A7D74E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a14bac90927db699ac4af297f1d406f2762c11d","datavalue":{"value":{"entity-type":"item","numeric-id":168581,"id":"Q168581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$FF797758-D6DA-4D2B-A5B8-1B4D51DD27A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a40a7c874481a1a229f505dcfb1443755c75490","datavalue":{"value":{"entity-type":"item","numeric-id":1175548,"id":"Q1175548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$CE3AD5B8-5E99-459E-8941-0D649A7543BD","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":"Q631642$0E8F029E-DA90-41B7-8C9C-F2C74321EA5D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4f05c15c599566c03aa1303bff626bf49bc05676","datavalue":{"value":{"time":"+2011-03-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q631642$17BBB564-C496-4139-94E8-BFF7826AFFB8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f6501c2c9e01ef26307102daa4fe7375b8d7e0fa","datavalue":{"value":"This paper is one of a series of papers in which the authors investigate a classic problem in extremal graph theory: Given a family \\(L\\) of `forbidden graphs', determine the maximum number of edges that a graph can have on \\(n\\) vertices, not containing any member of \\(L\\) as a (not necessarily induced) subgraph. More precisely, the authors are seeking a characterization of the set of \\(L\\)-free graphs, and to establish a relationship between the set of \\(L\\)-free graphs and the subgraphs of the \\(L\\)-extremal graphs. This continues the line of research started by \\textit{P. Erd\u00f6s, P. Frankl} and \\textit{V. R\u00f6dl} [``The asymptotic number of graphs not containing a fixed subgraph, and a problem for hypergraphs having no exponent'', Graphs Comb. 2, 113--121 (1986; Zbl 0593.05038)].    In this particular chapter of the series, the authors concentrate on the octahedron as forbidden graph, and they prove several results about the typical structure of octahedron-free graphs, such as:    1. The vertex set of almost every octahedron-free graph can be partitioned into two classes of almost equal sizes, \\(U_1\\) and \\(U_2\\), where the graph spanned by \\(U_1\\) is \\(C_4\\)-free, and the graph spanned by \\(U_2\\) is \\(P_3\\)-free.    2. Similar assertions hold when \\(L\\) is the family of all graphs with 6 vertices and 12 edges, so that in some sense, the octahedron is a representative of that family of graphs.    The style of the paper is quite technical, and it is worth noting that the authors have kept the same terminology and notation throughout the whole series.","type":"string"},"datatype":"string"},"type":"statement","id":"Q631642$BE827345-C73F-4A2C-80AA-1CE35460CABC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"83ea1119a5eba74d0e2ceda74e470cb249630932","datavalue":{"value":{"entity-type":"item","numeric-id":283698,"id":"Q283698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$6DC35D09-582E-4D3D-8B31-E2922FE2BBD0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631642$6E8E46EE-A96A-42A1-B6C9-104BB02B36F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ff9d350acea12ffd75e7ed8da6f45c48ff041eef","datavalue":{"value":"05A20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631642$3D431319-3066-4C82-91DB-01094182AF3C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"379edd410b911b8a8ce52742a5eca69421db5d6c","datavalue":{"value":"5865467","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631642$D55CB3FA-DCEC-45CD-81F0-E5F9D44A822D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bdefd4725d91bba1e0d0861018fdd0e81ad28b3","datavalue":{"value":"extremal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q631642$CAAAC5A7-85B7-4516-A479-1DD6740F7A12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f51251e85b413186c9529babb5a0d00a0d4276b","datavalue":{"value":"structure of \\(H\\)-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q631642$F3610E59-C9B1-4CC7-810E-BB6506412F6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6afa4f30b90f8b10f99eb5e74a123b4892f4beac","datavalue":{"value":"graph counting","type":"string"},"datatype":"string"},"type":"statement","id":"Q631642$D076A85B-B55D-4EC2-9FA8-733367C42144","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":"Q631642$D6189AE0-9D80-4506-A3EB-3982714AE8C8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"acf91982712f60c578c29ba8752228fd5cc8b047","datavalue":{"value":"https://doi.org/10.1016/j.jctb.2010.11.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q631642$7F5B90BC-4374-4C7A-A964-4FC10226B268","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"86536becffdfb1e0b6bccb505e8dda329556420d","datavalue":{"value":"W2047564915","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631642$8B529783-24CE-40AD-9469-FE41B227491C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9dab0e5dc0039cf14128fe5cf3cfbdad5be60d6","datavalue":{"value":{"entity-type":"item","numeric-id":631643,"id":"Q631643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$0723E4C3-87D2-45E8-921B-B8A6A56B2D61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a355ea13c3ed372b34436d05518ee3ae9aa00744","datavalue":{"value":{"entity-type":"item","numeric-id":1826950,"id":"Q1826950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$279E921E-EC25-49C7-BACC-424436A61C96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b019a379fc01faedb5cf672f77fc7c9024f49de1","datavalue":{"value":{"entity-type":"item","numeric-id":3633015,"id":"Q3633015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$9149EE4F-14A8-44D1-A776-4C5D7930031E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cc4bc477186350788c2b682172ab41f1f0c7c2d","datavalue":{"value":{"entity-type":"item","numeric-id":3068762,"id":"Q3068762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$B3B30D56-8737-4819-8822-17D99BD959B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4abb591e2821a070c3f5f1804c8e042255b8fbb5","datavalue":{"value":{"entity-type":"item","numeric-id":3008023,"id":"Q3008023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$83ABFA89-7EC9-465C-9076-7AB965DE8EC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8402909d7c243f063788852ea31591eef8f9b30","datavalue":{"value":{"entity-type":"item","numeric-id":5392190,"id":"Q5392190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$509D2135-EB65-4D5E-BDE5-AAD9333ACBA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90a4350076ed9491a64ad37f39546f09a185eedc","datavalue":{"value":{"entity-type":"item","numeric-id":2563170,"id":"Q2563170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$93E85666-971E-4419-B07E-E49CDF4614F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fabbf965c27bc37cda71868cb575f124f46c9596","datavalue":{"value":{"entity-type":"item","numeric-id":5720206,"id":"Q5720206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$262588D8-C7A7-475B-8CC7-E53FBB816B36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"345c41968f3aeebd152e751368a44b16d079dc5f","datavalue":{"value":{"entity-type":"item","numeric-id":1076037,"id":"Q1076037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$FD8D8F39-C07D-405F-8340-B9482B748DC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbc11b24c5af9cef6418bda6795148fabd885cf1","datavalue":{"value":{"entity-type":"item","numeric-id":5520566,"id":"Q5520566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$7D7A4FFC-63E6-4C32-8EC0-B1251E2702F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dd1d1ccfad9724b54b7447938854d4633418a80","datavalue":{"value":{"entity-type":"item","numeric-id":5642586,"id":"Q5642586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$0B6649DF-7E8E-4106-89C7-568721DE100F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02aa720f0fa82e3addfed9feff58641822d76a93","datavalue":{"value":{"entity-type":"item","numeric-id":1837701,"id":"Q1837701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$11CAD2BA-EC85-409D-9F15-79A6B41555E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"926e901fda1d453e47538fe39c14ad844730359c","datavalue":{"value":{"entity-type":"item","numeric-id":1318835,"id":"Q1318835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$D4A3FF2D-42AD-42B7-82D7-FAE706905BAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b4361b1b2aad0e6ca0d5d5fbcdbcd322af0004f","datavalue":{"value":{"entity-type":"item","numeric-id":4242962,"id":"Q4242962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$3C61544C-49B8-4F9E-B86D-59FDC668A173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b9ad0745eeb1a5992c2ac50f85cc1c770cf4302","datavalue":{"value":{"entity-type":"item","numeric-id":1167182,"id":"Q1167182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$EE9C8D1D-87CE-47F3-98FD-7E2C8528D235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63ada53980e8d3e7e8a0a401742a431780860804","datavalue":{"value":{"entity-type":"item","numeric-id":5825672,"id":"Q5825672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$37A9C93A-74ED-48E8-A710-463BFBE9D197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28d2f14884ef125ae62acadbca226de4bffc87cb","datavalue":{"value":{"entity-type":"item","numeric-id":1204522,"id":"Q1204522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$C1C2D45B-78BE-4228-9992-153AE83F5D1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28d4ed8388f5bc6b9907b07191ce55da1c665437","datavalue":{"value":{"entity-type":"item","numeric-id":4175585,"id":"Q4175585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$BB951C86-9C35-43E2-B76E-7092CD2B0C52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"887ce430b000ffd8813e06446b140ace91a67a26","datavalue":{"value":{"entity-type":"item","numeric-id":5548826,"id":"Q5548826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$25BE8F36-DA6A-4C47-BC72-B98F511463CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddb96bdc1c0d2fdfc352b10e5c01ed264295afa2","datavalue":{"value":{"entity-type":"item","numeric-id":2264683,"id":"Q2264683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631642$2A8EAED1-9956-41F1-BC76-4A10E08F7514","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"73b8030b02124f263f9fc1230d44603fe372f1e2","datavalue":{"value":"10.1016/J.JCTB.2010.11.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631642$0E5DC3FD-B6B1-4490-902C-1F0FBEA4BA42","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef5876a6bbd322f96be10f4dddd6abfdd63c511f","datavalue":{"value":{"entity-type":"item","numeric-id":3633015,"id":"Q3633015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6788e4d03346ff1e7c5063cafd60eaecdce48818","datavalue":{"value":{"amount":"+0.7448814511299133","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":"Q631642$689EB7DD-8F9F-41A2-B8D9-5051BD9238A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e28beccd25cf1df71e8451a8f913a6aa16fa7bf9","datavalue":{"value":{"entity-type":"item","numeric-id":4154888,"id":"Q4154888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e577343facde1fb8b78de18ff4f2859cc52a810d","datavalue":{"value":{"amount":"+0.7406423687934875","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":"Q631642$D3531883-02E3-457B-9836-820331271504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b11a765776bf925d7325552ba0a4036c55887db6","datavalue":{"value":{"entity-type":"item","numeric-id":2236656,"id":"Q2236656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46f00b233c0f2fff83d05efa20eec90fed285cfb","datavalue":{"value":{"amount":"+0.7384592890739441","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":"Q631642$139788DA-8723-4F3C-B1F7-18439930441C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2743c6a2a38c08dd74d43cfaa660aca2696bed57","datavalue":{"value":{"entity-type":"item","numeric-id":1322244,"id":"Q1322244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5c2504bfe5226deaf364ba3e54d596856fbaf6a","datavalue":{"value":{"amount":"+0.737886369228363","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":"Q631642$67BC7AB6-EEBF-4593-AA19-25F06043C132","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e194504498defe72cc53e439aa626e4d929e4587","datavalue":{"value":{"entity-type":"item","numeric-id":1826950,"id":"Q1826950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d465b3f67955137a504902cadc11ddcd69fc77c8","datavalue":{"value":{"amount":"+0.730112612247467","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":"Q631642$DD830BA1-C4FC-4EAB-99BA-3FB4EDB640C6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:631642","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:631642"}}}}}