{"entities":{"Q1363652":{"pageid":1374391,"ns":120,"title":"Item:Q1363652","lastrevid":68730561,"modified":"2026-04-13T01:42:24Z","type":"item","id":"Q1363652","labels":{"en":{"language":"en","value":"Independent sets and repeated degrees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1047045"}},"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":"Q1363652$99DEDCF2-44BB-49B4-85F4-3330985AF0F3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"478a3332a1c80f87f614bc4bb196990d43fead78","datavalue":{"value":{"text":"Independent sets and repeated degrees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1363652$9BFD86FC-1AA4-4AA0-8AD2-CFFE568CDFEF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b4b6c6ba9cb426d806d29316daa491a5e073d96a","datavalue":{"value":"0881.05071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363652$AB819F11-600F-4B52-A76D-F0B34D0EE067","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cb59dd4f67935d63c0af836885e36aa6c06debc3","datavalue":{"value":"10.1016/0012-365X(95)00355-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363652$B48B5606-ACB2-455C-B750-F985E29B57DA","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":"Q1363652$D545CA21-FF55-4959-9831-98787ED1F077","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"24fb4fe71a2595983b723d9da5040cfe01165fe6","datavalue":{"value":{"time":"+1998-02-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1363652$D48FFB4F-BF56-4232-B3B4-0D45867521F1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8eb826323f413f295e79232ee589a992493e0022","datavalue":{"value":"\\textit{P. Erd\u00f6s}, \\textit{S. Fajtlowicz} and \\textit{W. Staton} [Discrete Math. 92, No. 1-3, 85-88 (1991; Zbl 0752.05028)] showed that every triangle-free graph of order \\(n\\) in which no degree is repeated more than twice is bipartite and thus has independence number at least \\(n/2\\). \\textit{P. Erd\u00f6s}, \\textit{R. Faudree}, \\textit{T. J. Reid}, \\textit{R. Schelp} and \\textit{W. Staton} [Discrete Math. 141, No. 1-3, 275-290 (1995; Zbl 0833.05074)] asked for triangle-free graphs of arbitrarily large order with no degree repeated more than \\(k\\) times and having independence number \\((1+o(1))n/k\\); they showed the existence of such graphs for \\(k=4\\) also. Here the authors give a probabilistic proof of the existence of such graphs for all \\(k\\geq 2\\). They close with several interesting questions and a conjecture.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363652$54A4FCA3-A5C0-46B1-8CD0-70D971285BF2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363652$EDC3C7C7-7CB2-4D85-A56D-586F4CD17121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363652$4FDDE22F-0306-419C-93E2-4BFCFAA39845","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"beea1226de7a7dff9ca155c25d4b6dd014012f05","datavalue":{"value":"1047045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363652$0D6DC8E6-60DB-4260-9819-68AA6968426D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9890d2d31de82fcf86b74b799289b36efeaabea2","datavalue":{"value":"independent sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363652$8EE7D08E-7BAE-4192-91C2-84B09BEF5C36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d08e4e9f0d1f969665f71bdb1a46f004b6ce4397","datavalue":{"value":"repeated degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363652$11352417-C26B-484D-A1D0-FFDA52244E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ce67bd27fc3ee89d8642921735100b79f0d0ab3","datavalue":{"value":"triangle-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363652$6B484FC2-1566-41AA-AFC2-3C4548022396","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b89aa1b9eed71217ebf6a719487a219071558409","datavalue":{"value":"independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363652$C30C7AB0-4953-4661-8D8E-F613B16570FD","rank":"normal"}],"P16":[{"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":"Q1363652$D25D59FE-EEE2-4E5D-9A03-6D12A595270C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f8b2beaa85ff67f6ba8323eb17002460f5e5f0aa","datavalue":{"value":{"entity-type":"item","numeric-id":846045,"id":"Q846045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363652$4B6428A8-7A36-430D-BB80-04FBCDBA4700","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4160ba73cc613e2769e008ae8a9ce69c96d8603f","datavalue":{"value":{"entity-type":"item","numeric-id":207053,"id":"Q207053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363652$7F5D6EE1-9698-4DEF-8546-6CAD62D7AEB4","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":"Q1363652$538DB9B4-9C5C-45ED-AC31-B6ABB7E13819","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cdeea2ccd0d967feaab81a8c6de46c527314240","datavalue":{"value":{"entity-type":"item","numeric-id":1182926,"id":"Q1182926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363652$9A76AA7F-6875-4105-8AF8-AD8B45FAA818","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2619224364c48c3d3047e28dd0831019304562ed","datavalue":{"value":{"entity-type":"item","numeric-id":1894779,"id":"Q1894779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363652$3FEDCD44-5702-44F2-B99E-5D3045E8760C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"569bcf54bf82d150623a05328f65cc21905f158b","datavalue":{"value":"https://doi.org/10.1016/0012-365x(95)00355-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q1363652$58A38DDD-44E6-4E9D-A5FF-9F8F36539870","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8feb96facd07310b648f4a258ab12ad73bc2f6b7","datavalue":{"value":"W2104082818","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363652$13C18369-D977-40B2-B9EA-5606EE5E654B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0dcc094b27355f9936556a5536a9ece8de93bbc5","datavalue":{"value":{"entity-type":"item","numeric-id":1182587,"id":"Q1182587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21a126f1cf8fb0fe95804669a90dbbdc02778da1","datavalue":{"value":{"amount":"+0.8256383538246155","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":"Q1363652$2D664EA6-21BA-412E-BDCA-6E6B1947CEAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8f1a093d248c89d96c592583163403acc0cf669","datavalue":{"value":{"entity-type":"item","numeric-id":4712120,"id":"Q4712120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9ddc7a8f4f911e633ad849e9799c99b185234e4","datavalue":{"value":{"amount":"+0.8164753913879395","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":"Q1363652$5BBB4343-8122-461C-9031-A51DB0CAD8BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a7957fefcb39ae08355002c5449a1a82346e49c","datavalue":{"value":{"entity-type":"item","numeric-id":1186139,"id":"Q1186139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b529c81f7a26a73b2c29642a031f9e01db856222","datavalue":{"value":{"amount":"+0.8148449063301086","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":"Q1363652$E4BE3DBB-075F-44CB-A625-4E0C3FE8C6FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26b77e16edf1cf2c3a07d2f8f67985bc691b67fe","datavalue":{"value":{"entity-type":"item","numeric-id":932585,"id":"Q932585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71512ce14bd2b5f5613d1c66740a0eae2f54c3dd","datavalue":{"value":{"amount":"+0.8121110796928406","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":"Q1363652$62A1C072-27CE-49C0-B606-CF863C87C9EF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Independent sets and repeated degrees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Independent_sets_and_repeated_degrees"}}}}}