{"entities":{"Q6057487":{"pageid":13191642,"ns":120,"title":"Item:Q6057487","lastrevid":58663620,"modified":"2026-04-06T05:52:22Z","type":"item","id":"Q6057487","labels":{"en":{"language":"en","value":"Minimum degree stability of \\(H\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7745870"}},"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":"Q6057487$BA69EB94-3BC1-4B83-AC2E-3C8CAFB29333","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bd29d44985abad2f7436bca31da68fe5b5a374e6","datavalue":{"value":{"text":"Minimum degree stability of \\(H\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6057487$F5FB29EF-592F-4143-B517-9C445D1550DA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"150cb9c162661be955935978a167227b198180d5","datavalue":{"value":{"entity-type":"item","numeric-id":2223472,"id":"Q2223472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6057487$A6462407-60A5-43B8-A46E-DD697A8C661C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6057487$8E7BA3C0-0733-49F5-9625-7E00A61455AF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31c936eef8b332040242af2e27eaff5bc37458f1","datavalue":{"value":{"time":"+2023-10-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6057487$C916E756-9987-4BFF-8518-FA4692D1354D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1cf0943bfd3f8e8a0f496cc0008fd90a3eabf74c","datavalue":{"value":"https://arxiv.org/abs/2102.11104","type":"string"},"datatype":"url"},"type":"statement","id":"Q6057487$D5F5E455-AA3F-4196-82EC-F9474309BCBA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"29b1aff4a8375a16c087416bed0cd4c56d8cc6c0","datavalue":{"value":"\\textit{P. Erd\u0151s} and \\textit{M. Simonovits} [Discrete Math. 5, 323--334 (1973; Zbl 0268.05121)] showed that if \\(H\\) is a fixed graph with chromatic number \\(\\chi(H)=r+1\\), then \\(H\\)-free graphs \\(G\\) on \\(n\\) vertices have at most \\(\\left(1-1/r+o(1)\\right)\\binom{n}{2}\\) edges, and any graph on \\(n\\) vertices which has \\(\\left(1-1/r+o(1)\\right)\\binom{n}{2}\\) edges can be obtained from the \\(r\\)-partite Tur\u00e1n graph by adding and/or deleting \\(o(n^{2})\\) edges. In particular, it is close to being \\((\\chi(H)-1)\\)-partite.\\par It is now natural to ask if \\(H\\)-free graphs on \\(n\\) vertices with minimum degree \\(cn\\) are close to being \\((\\chi(H)-1)\\)-partite. Define \\(\\delta(H)\\) to be the infimum of all \\(c\\) such that every \\(n\\)-vertex graph \\(G\\) with minimum degree \\(\\geq cn\\) can be made \\(H\\)-free by deleting \\(o(n^{2})\\) edges. For example, \\textit{B. Andr\u00e1sfai} et al. [ibid. 8, 205--218 (1974; Zbl 0284.05106)] showed that \\(\\delta_{K_{r+1}}=1-1/(r-1/3)\\). \\textit{N. Alon} and \\textit{B. Sudakov} [Electron. J. Comb. 13, No. 1, Research paper R19, 9 p. (2006; Zbl 1085.05036)] observed (more than) the fact that if \\(H=K_{r+1}(t)\\), a complete multipartite graph with \\(t\\) vertices in each of the \\((r+1)\\) classes, then \\(\\delta_{K_{r+1}(t)}=1-1/(r-1/3)\\). Now, of course, this implies, as any \\(H\\) with \\(\\chi(H)=r+1\\) is a subgraph of \\(K_{r+1}(t)\\) for some \\(t\\) that \\(\\delta_{H}\\leq 1-1/(r-1/3)\\), however, the inequality may be strict, so accurate estimates of \\(\\delta_{H}\\) are desirable. \\par For 3-chromatic graphs \\(H\\), the paper under review shows that \\(\\delta_{H}=2/(2g+1)\\) where \\(g\\) is the smallest positive integer for which there is not a homomorphism \\(G\\longrightarrow C_{2g+1}\\) where \\(C_{r}\\) is the cycle of length \\(r\\). The result for \\(H\\) whose chromatic number is greater than 3 is more complicated. It is that there is a sequence of eleven graphs \\((F_{g})_{g=1}^{11}\\) and eleven constants \\((c_{g})_{g=1}^{11}\\) such that if \\(r\\geq 3\\) and \\(H\\) has chromatic number \\(r+1\\) then if \\(g\\) is minimal such that there is no homomorphism \\(H\\longrightarrow K_{r-3}+F_{g}\\) (here \\(+\\) denotes join) then \\(\\delta_{H}=1-1/(r-1+c_{g})\\). If instead there is a homomorphism to all eleven graphs \\(K_{r-3}+F_{g}\\), there will be a least \\(g\\) such that there is no homomorphism \\(H\\longrightarrow K_{r-2}+C_{2g+1}\\) and we then have the bounds \\[1-\\frac{1}{r-1+2./(2g-1)}\\leq \\delta_{H} \\leq 1-\\frac{1}{r-1+1/7}.\\] The parameter \\(\\delta_{H}\\) is also put into the context of approximate chromatic profiles. Proofs make much use of the regularity lemma and associated machinery.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6057487$77E75BA5-4798-4A45-BDA7-E195EB2BF057","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0b0cea8603b4de1ffd54cda6d37d129691a25c2","datavalue":{"value":{"entity-type":"item","numeric-id":590772,"id":"Q590772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6057487$AF4B3737-C84E-46E5-8FAD-B71FA7E0DEA1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6057487$F909F34F-1B10-4BBA-BB4C-E7110FA686F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6057487$0EA452B2-A638-41D7-B284-E6F6125ECF5F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"758be0235a6762ec397631dd7336c35ee2e37613","datavalue":{"value":"7745870","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6057487$1AE786B7-F747-4D32-A458-DCD89082AB1E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"013a665df3872df6518b386ba286fc369d4eed69","datavalue":{"value":"extremal graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q6057487$DC235879-FC50-4FD1-A078-37B47C004DF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34b44e7b40021effdee26093512bde7058814281","datavalue":{"value":"stability","type":"string"},"datatype":"string"},"type":"statement","id":"Q6057487$545577F6-7DB4-4708-AF44-042DCFA83859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e994072af1a35832ce5b62d5f5b0fc2c1e20c792","datavalue":{"value":"chromatic profiles","type":"string"},"datatype":"string"},"type":"statement","id":"Q6057487$C6FD241C-2730-47AE-8527-3DCC6F29316A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"331ee4ea35d19312d8f9bd00934489fe6fd4132b","datavalue":{"value":"chromatic thresholds","type":"string"},"datatype":"string"},"type":"statement","id":"Q6057487$801B4976-75FA-4C7A-9EC9-9968DA577989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59e104fc9083dc8c4e491b340ba5128d82bfc9b1","datavalue":{"value":"colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6057487$22D3B078-F933-402C-BB53-123C496DC98C","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":"Q6057487$61EB49C3-EB4C-40A5-BA7E-4AF61361D5BB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2f803253bafc4d86de45df995bf870f615dc5562","datavalue":{"value":"W3133426009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6057487$DB6780D5-2706-4D37-97AD-18026815226E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"78e3d3ab274ed77be94c7a31f22d3808e492717b","datavalue":{"value":"10.1007/S00493-023-00010-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6057487$A4E8D82C-D290-4B01-B67C-2C6CB3BDA5A8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0eef9c13974daaba27a8d7599c7dd7dbccf382ea","datavalue":{"value":{"entity-type":"item","numeric-id":819178,"id":"Q819178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"500fd6b0fbe449fee7126962aa04a6adc7bb80fb","datavalue":{"value":{"amount":"+0.8705945611000061","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":"Q6057487$C4897C8B-3416-4C9A-92E2-F5BA6DA25D65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2124769dd8cd5296b3e895bad1a4225ed5153d2f","datavalue":{"value":{"entity-type":"item","numeric-id":1941151,"id":"Q1941151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d967c7dc708c0a2d511163f0f30513838379515b","datavalue":{"value":{"amount":"+0.8447574973106384","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":"Q6057487$A870C717-CDA9-40B7-9DF5-93EE24C51BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce007c1463ca0920ef39d0316c2000a9899b7846","datavalue":{"value":{"entity-type":"item","numeric-id":858147,"id":"Q858147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12ae529166435b56fed49027ba0ef02b7f416228","datavalue":{"value":{"amount":"+0.8374407291412354","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":"Q6057487$44C13319-8374-4E3A-83AF-4875643A19CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e12340f9249803648a8f808cb11598f82064bb9d","datavalue":{"value":{"entity-type":"item","numeric-id":2380453,"id":"Q2380453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2becbc8403e9920989cc1e94dbf9bf421eadd82d","datavalue":{"value":{"amount":"+0.836859941482544","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":"Q6057487$C88A1EFE-A3EA-43A5-8DCA-78106195E068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2abd3d4649e02f75461854cd9532bfcdab8da4c","datavalue":{"value":{"entity-type":"item","numeric-id":3168661,"id":"Q3168661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60df182e246d388f494003401df1b4ecce95ab30","datavalue":{"value":{"amount":"+0.8134487271308899","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":"Q6057487$5151E9CE-20A4-4508-B4CB-12E6B1EFD502","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6057487$94847C1F-8C7B-441A-BE01-F4B728612409","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6057487","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6057487"}}}}}