{"entities":{"Q2583671":{"pageid":2594414,"ns":120,"title":"Item:Q2583671","lastrevid":44403168,"modified":"2025-11-22T17:10:53Z","type":"item","id":"Q2583671","labels":{"en":{"language":"en","value":"Degree sequences of \\(F\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2248141"}},"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":"Q2583671$B971A23F-02BC-4C70-978B-4DFF51735704","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"43015e99b75fe7acb991af99d2847b99e1c8b24a","datavalue":{"value":{"text":"Degree sequences of \\(F\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2583671$CB7CAECF-785E-48CC-A232-71470D17A108","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0b33496daf66fe17f5e2a2975e46ce644cffe708","datavalue":{"value":"1082.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2583671$38DA4EC3-4A06-4DFC-8E2D-911F30D4AF0E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7dab6f8db6330a54d865eb55c2e58b9f4644f01","datavalue":{"value":{"entity-type":"item","numeric-id":228798,"id":"Q228798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2583671$01AB71A8-260A-43E9-9731-FC82BF64768F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a8d1ab6fcc45f42748a5a279dda378426d59803a","datavalue":{"value":{"entity-type":"item","numeric-id":175601,"id":"Q175601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2583671$7472D77F-98CA-42A7-8AC3-20CD5AADAA3F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2583671$51C08668-8938-4ACC-BDF2-AA91513F8644","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b4df1b8b5707fc4a42b8f50fc6476f3b8f097b1e","datavalue":{"value":{"time":"+2006-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2583671$2E663B0E-4E46-4DBD-8951-4A5A5F3DF681","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9f1ddf9d32f8f603229cb9ff984c4eedf1f2c1ac","datavalue":{"value":"https://eudml.org/doc/125634","type":"string"},"datatype":"url"},"type":"statement","id":"Q2583671$703F3C28-A134-4452-9EB0-415CC89286CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"4124fa89502da160c960dde9ffbb093c90648a68","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_12/Abstracts/v12i1r69.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2583671$EAE512E8-B773-4B9E-B023-888540FEAAA4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"357cb23bef08a6819c534a58b40671e6f7c7d3ac","datavalue":{"value":"The Erd\u0151s-Stone theorem states that, for an arbitrary graph \\(F\\) with chromatic number \\(\\chi(F)=r+1\\), it holds that  \\[ \\text{Max}\\bigl\\{e (G):\\nu(G)=n,\\;F\\subseteq G\\}=t_r(n)+o(n^2)\\geq(1-1/r)n(n-1)/2, \\]  where \\(t_r(n)\\) is the number of edges of the Turin graph \\(T_r(n)\\), namely the complete \\(r\\)-partite graph on \\(n\\) vertices with parts as equal as possible. In other words, for every \\(F\\)-free graph \\(G\\) of order \\(n\\), there exists an \\(r\\)-partite graph \\(H=T_r(n)\\) with almost as many edges as \\(G\\). In the present paper, the authors consider the question whether analogous statements are true if one compares the degree sequences instead of total number of edges. They prove the following main theorem: Let \\(F\\) be a fixed non-empty graph of chromatic number \\(\\chi(F)=r+1\\). For any \\(\\varepsilon >0\\) and large \\(n\\geq n_0(\\varepsilon,F)\\) the degree sequence \\(g_1\\geq\\cdots\\geq g_n\\) of any \\(F\\)-free graph \\(G\\) is \\((\\varepsilon n,\\varepsilon n)\\)-dominated by the degree sequence of some \\(r\\)-partite graph \\(H\\) of order \\(n\\). Two proofs of the main theorem are presented allowing for some technical improvements.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2583671$D51568DE-35AA-4707-AE35-47A37C607571","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2583671$E27C81EA-F77E-4449-9B21-33E6CD472632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2583671$9E3E4B07-2867-4AB0-82E5-15F7169CDEFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2583671$3E995E4B-300C-4181-AB31-BD1979083E96","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f4b4fd90461dcc298fffbef89840406b54bb8dd4","datavalue":{"value":"2248141","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2583671$A2897DBA-B2AA-4BC3-8D49-FE6667E9CBFF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2bf5853e390c5a1805693ce1a32a331c7a6744b6","datavalue":{"value":"Turin graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2583671$F64AC8AC-CF4D-4A83-82B0-E4F5BA7D5407","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"201ad656abc019d10a6412dc1d67c714881069e3","datavalue":{"value":"Erd\u0151s-Stone theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2583671$7BB96E01-3E1A-4FB2-B793-5BD2DB484133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2583671$71DE0F3A-718C-4A92-AE67-3F93B27B23F6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9d66e90f972a7f51f6383d3d2a8f96ff1d055d08","datavalue":{"value":{"entity-type":"item","numeric-id":924946,"id":"Q924946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2583671$17346493-63BD-4294-9C02-33D156C440A8","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":"Q2583671$108903EB-A0ED-44CB-B883-B4C7005D9310","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"3d44dfa8c80f998aff530c8d90d1231d1f616574","datavalue":{"value":"bafkreid5t54kpdujsme2b4363p3z6tib3xlmpatscqqgbq2qyrt4wdxphm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2583671$8F08C24B-FD3D-4014-AD69-42F33A8F327A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08df4a979788ebc337d461a240f9d0bc9303dd5f","datavalue":{"value":{"entity-type":"item","numeric-id":1182926,"id":"Q1182926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c114bc41e754aea76dcc6c599952c21e471c0185","datavalue":{"value":{"amount":"+0.94796693","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":"Q2583671$F72EA187-2E1E-445C-82CA-C82D209E69DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be701bebe0b700b22d6fd4f60f0076e86f80c4b4","datavalue":{"value":{"entity-type":"item","numeric-id":4320263,"id":"Q4320263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9145988a9fc31b42e4285906a6a18ef8f8dbe85","datavalue":{"value":{"amount":"+0.9141184","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":"Q2583671$5CD96672-4697-4210-AFAF-0D93EEE9D22B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4b7c986a5b1bfaa0c8a82cc83a7642bee4d95ef","datavalue":{"value":{"entity-type":"item","numeric-id":1894779,"id":"Q1894779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b88e96917cb989eed13389cfa83afa191f36fa3","datavalue":{"value":{"amount":"+0.9103989","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":"Q2583671$0A6DF541-3831-4B0B-B073-21D1959D68D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67076eab096200b9b0b982768c01c6573dc5436b","datavalue":{"value":{"entity-type":"item","numeric-id":3153162,"id":"Q3153162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02f09035d28ea5a421ee8e010a773f7ce9c98eda","datavalue":{"value":{"amount":"+0.907949","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":"Q2583671$2159E4CA-C611-4188-A479-34337378C702","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2643409778ef3cd48a65ca249a2a58fb814be023","datavalue":{"value":{"entity-type":"item","numeric-id":5472665,"id":"Q5472665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4602482975fb13becba9e0df0b109a3e462103a","datavalue":{"value":{"amount":"+0.90726364","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":"Q2583671$93CE962A-85C8-426F-AE2E-613C60D6B60B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65002e8deb1cb201f08f4da7dc66b1b93e284fa3","datavalue":{"value":{"entity-type":"item","numeric-id":2898817,"id":"Q2898817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0af0c2ec2a549e8939c4330ab471b1ee66c22c5d","datavalue":{"value":{"amount":"+0.9004837","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":"Q2583671$7708978B-30DB-4DAF-8D58-FF6EB247D31E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"623b3098930ff278ce61be2d3da798791534ba69","datavalue":{"value":{"entity-type":"item","numeric-id":2834249,"id":"Q2834249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"574e8b11d0dc43205a0050d4c8cf276faab0f587","datavalue":{"value":{"amount":"+0.9004836","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":"Q2583671$46E0C1A0-D318-4320-B544-D82343D7A1C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc64dcd8a387a17b83cd1335061f0a2f9bd1ad44","datavalue":{"value":{"entity-type":"item","numeric-id":1865147,"id":"Q1865147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35d4f381777b03114ca068f461b9e55b3dfac484","datavalue":{"value":{"amount":"+0.89989734","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":"Q2583671$CD9E964E-8462-401D-B0EB-82D6F3023A4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd6cd8ec2a1cc2e0c7f4e060786b860fbf60a3aa","datavalue":{"value":{"entity-type":"item","numeric-id":4597162,"id":"Q4597162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13ce802b67e9f9be38ea1731b527c57351d960a6","datavalue":{"value":{"amount":"+0.89842093","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":"Q2583671$5EC3C097-9D29-4F3A-892F-411C9D37BB4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea3d6e39a523d0ce47bb9c7c333db454b17c6945","datavalue":{"value":{"entity-type":"item","numeric-id":3784108,"id":"Q3784108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"710b7d65709a89ed60719a61a009467ea696a3d6","datavalue":{"value":{"amount":"+0.897006","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":"Q2583671$85CF9C9E-F565-48A6-AEB6-743BDFD73937","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2583671","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2583671"}}}}}