{"entities":{"Q2748425":{"pageid":2759164,"ns":120,"title":"Item:Q2748425","lastrevid":47687659,"modified":"2026-01-02T10:44:09Z","type":"item","id":"Q2748425","labels":{"en":{"language":"en","value":"On the structure of clique-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1659414"}},"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":"Q2748425$8D655D60-6BAE-45F0-BD68-6A601C223B5C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1a3dcc4196121b5e9b885cb78d3c3e1ebb63edff","datavalue":{"value":{"text":"On the structure of clique-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2748425$1BE46BEE-8BF7-4638-9D63-4B4852D2C073","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c143f5ef15fc6a82be2e13d419cf9e3c5855b9d4","datavalue":{"value":"0989.05107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2748425$5767A8DE-6939-4D75-B0D9-19AF609B441C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7f7828d89a9ab7dcac53cfa0b07091daf4925321","datavalue":{"value":{"entity-type":"item","numeric-id":171728,"id":"Q171728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2748425$BA6A90BD-6C17-4C8D-9EAE-88FF358DDA17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8114b1347065a26451fcad70667548a886237e8c","datavalue":{"value":{"entity-type":"item","numeric-id":190242,"id":"Q190242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2748425$66599A32-598E-4290-BE6B-FDB592FBBEC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a7b1b74b045e21f161107ae2d1ec32cd3fa125c","datavalue":{"value":{"entity-type":"item","numeric-id":173496,"id":"Q173496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2748425$9FAE18F5-52E0-452E-9807-E5D845EF1966","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"64c1f5c2d2acc8630c4745adbe761e7f69f976b3","datavalue":{"value":{"time":"+2001-10-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":"Q2748425$E08CDB19-0016-451C-A32A-AE459FBBC30B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2748425$06860F44-FC6F-4CBC-B228-C0A621EC2D78","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d79746671a4af42938ab9507968244b5d71835c8","datavalue":{"value":"1659414","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2748425$971E113E-C1AD-4509-A169-788343C6A667","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eecb173004633ca38efc326bcd073800d8b745c9","datavalue":{"value":"bipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2748425$548C4735-5FC5-4F19-AC6D-6AF9792FE84B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"938507bc54d83812726579a12a77d5cd2af4ae8b","datavalue":{"value":"triangle-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2748425$194334EE-5948-44D5-977F-EDFDB94B5097","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":"Q2748425$F1F6C98A-A97F-42E2-B4B4-A1B874F2B05B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b56044261162e4d544a7819fa0d8f9246fac83f8","datavalue":{"value":"https://doi.org/10.1002/rsa.1017","type":"string"},"datatype":"url"},"type":"statement","id":"Q2748425$E59AF663-98D7-46AE-9D91-CAA744D10AC0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7f452bbc01a3079be77a3061dce71bb49cb8a701","datavalue":{"value":"W2041133760","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2748425$D0B6E109-E83E-4E84-9F11-32A26D97522F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec29126dd47cfccf978459659e06cf3a67d71a0b","datavalue":{"value":{"entity-type":"item","numeric-id":4401980,"id":"Q4401980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2748425$C173C337-5BAC-4EF4-BBF0-B2692F9A38C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7dde78a908c61e3ace4fd73996142414f3ba5aa9","datavalue":{"value":{"entity-type":"item","numeric-id":4055647,"id":"Q4055647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2748425$CB6DE74F-F845-495F-90D1-C3277113BEF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8603e95a59637f07853abdfa96637d0cfbb1d082","datavalue":{"value":{"entity-type":"item","numeric-id":3781776,"id":"Q3781776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2748425$0DFBED78-16DF-4B03-ADA2-75A7159D4957","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33597eb53d35de713b7f13306e07cf0a7a5da5c8","datavalue":{"value":{"entity-type":"item","numeric-id":5931454,"id":"Q5931454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2748425$A253C8AB-3C5E-43A9-B3DF-E7DCCE0ED1FC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7a9de123dbd7d990d71f923b3d209f9414992054","datavalue":{"value":"10.1002/RSA.1017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2748425$BF68B7B1-5711-4AE1-BDE7-FD347CC93C52","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"607ae7f7d11ced7a8909533172911c64cec6dcc4","datavalue":{"value":{"entity-type":"item","numeric-id":6486797,"id":"Q6486797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2748425$3DEB5EA9-E999-44D6-91D1-6D72C263FFA6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ed9fdb8a29ae357196aec4e9243722908cc41c3e","datavalue":{"value":"It is known that almost all triangle-free graphs are bipartite, i.e., that the cardinalities of the two graph classes are asymptotically equal. In this paper the authors investigate the structure of the ``few'' triangle-free graphs which are not bipartite. As it turns out, with high probability, these graphs are bipartite up to a few vertices. More precisely, almost all of them can be made bipartite by removing just one vertex. Almost all others can be made bipartite by removing two vertices, and then three vertices, and so on. The authors also show that similar results hold if one replaces ``triangle-free'' by \\(K_{l+1}\\)-free and bipartite by \\(l\\)-partite.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2748425$43AC566E-60D2-44B0-B20B-756FD21DBB27","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ba3efcb7de77d1bd49142f0373b838a01109e4e7","datavalue":{"value":{"entity-type":"item","numeric-id":584284,"id":"Q584284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2748425$6833AC79-F2EA-4216-B7EF-AF1462223624","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f9707ef83eed5aab3b5e09b80861f36f8e8a34a","datavalue":{"value":{"entity-type":"item","numeric-id":1850031,"id":"Q1850031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5e849bfe8a4518f5e3dbb0aa9355b604fd67715","datavalue":{"value":{"amount":"+0.920202374458313","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":"Q2748425$6F94C699-F307-45D5-9E2B-F3F364FB3F9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65c1cf0d862881c2ceaa40ae8c51ecf8272d866e","datavalue":{"value":{"entity-type":"item","numeric-id":4643311,"id":"Q4643311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"069e2e2ddf85b3a459bed4c74a7875cff4afcf3b","datavalue":{"value":{"amount":"+0.920162558555603","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":"Q2748425$A352F86F-E81C-4D32-BFFC-8EEF3A6A0983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce6ac8d27d98ae3ab9dbaefb461921afa0311068","datavalue":{"value":{"entity-type":"item","numeric-id":681594,"id":"Q681594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9607a7943c45e73a5ce71b37591e382509c0a6ac","datavalue":{"value":{"amount":"+0.8619827628135681","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":"Q2748425$E52E5A9D-E5BC-4FBC-8999-191921D6A01E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ff5998dd4e291a43bee96a487ebfab3295ccda2","datavalue":{"value":{"entity-type":"item","numeric-id":1878594,"id":"Q1878594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"158c5a78770bcb6ed479cd737cbdd0d25304c895","datavalue":{"value":{"amount":"+0.855125904083252","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":"Q2748425$FE2AC5B6-26F0-4178-91F9-543973EAA8A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31f1fef4a78d5b458ec20bd54fa883c80bda9ca9","datavalue":{"value":{"entity-type":"item","numeric-id":4865522,"id":"Q4865522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdcbeda79642b82a60a2310cacd498871fd500fe","datavalue":{"value":{"amount":"+0.8514910936355591","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":"Q2748425$1F0F4B48-0B47-46D6-9E0D-8D79C8C149F2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2748425","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2748425"}}}}}