{"entities":{"Q1901038":{"pageid":1911780,"ns":120,"title":"Item:Q1901038","lastrevid":69234792,"modified":"2026-04-13T05:39:43Z","type":"item","id":"Q1901038","labels":{"en":{"language":"en","value":"Triangle-free four-chromatic graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 810262"}},"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":"Q1901038$FF4F4332-E4A3-4D46-B44A-7E4CF22A7552","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"48644a50db68b6137f419e1db8ee78ac2de94b76","datavalue":{"value":{"text":"Triangle-free four-chromatic graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1901038$1559752C-8F80-4BE6-8F42-208923CE0573","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"54c0443067a69abae8fca9a412cd54e625d7c294","datavalue":{"value":"0841.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901038$B478E598-EFDF-46E5-9B4E-DEFC00E08CCA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f872bb51f9a63caec1408c8cd47006fad51cd592","datavalue":{"value":"10.1016/0012-365X(94)00063-O","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901038$78BD9E72-0566-43F3-A7EC-411BC6326650","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c0ea1327e67e10e490b7691adc0ceb6dc9042e80","datavalue":{"value":{"entity-type":"item","numeric-id":1272533,"id":"Q1272533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901038$C022E3E1-4A53-464F-A2EC-F0C69013BC6D","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":"Q1901038$CF77145F-405F-4B5A-AE72-FDE88935F521","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1ca13147794ee6248df993be52ba350f706942fc","datavalue":{"value":{"time":"+1996-07-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":"Q1901038$FC35481F-F84F-459D-BE7C-541F96770E9C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b21c9335356dd86bba55683a26c54df2b6ddbe39","datavalue":{"value":"Given natural numbers \\(r\\) and \\(t\\), let \\(n(r, t)\\) be the minimum order of a \\(K^r\\)-free graph \\(G\\) with chromatic number \\(\\chi(G)\\geq t\\). Let  \\[ \\psi(n, K^r, t)= \\max\\{\\delta(G)\\mid K^r\\subset G,\\;\\chi(G)\\geq t,\\;|G|= n\\geq n(r, t)\\}. \\]  \\textit{R. H\u00e4ggkvist} [Ann. Discrete Math. 13, 89-99 (1982; Zbl 0492.05047)] proved that  \\[ \\psi(n, K^3, 4)\\geq {10\\over 29} n\\quad\\text{if} \\quad 29|n. \\]  A nice example led H\u00e4ggkvist to conjecture that  \\[ \\psi(n, K^3, 4)= {10\\over 29} n\\quad\\text{if} \\quad 29|n. \\]  The main result of this paper is Theorem 9: For \\(n\\geq 11\\),  \\[ \\psi(n, K^3, 4)= \\begin{cases} {10(n- 3)\\over 29}\\quad & \\text{if } 29|(n- 3)\\text{ and } n\\geq 33\\\\ \\lfloor{10n\\over 29}\\rfloor\\quad & \\text{otherwise}.\\end{cases} \\]  H\u00e4ggkvist's conjecture follows from Theorem 9.   The author also published the paper [Comb. Probab. Comput. 2, No. 4, 479-490 (1993; Zbl 0792.05078)] studying the structure of \\(K^3\\)-free graphs \\(G\\) of order \\(n\\) with \\(\\delta(G)> {10n\\over 29}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901038$18C82B89-EF11-4360-B5FF-38C0B5056569","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901038$012B6787-9596-4338-BE9F-3C03260CAD2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901038$B9BC27E6-D4AB-46F1-9E8E-BC0F6CB2475C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901038$E7E1F9DD-51A1-4917-AA0A-24D0306031EC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8c4e34fc73ede007875e96d61ed02d742356d4b9","datavalue":{"value":"810262","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901038$E205F863-C827-4B27-8605-1E0D42E2862B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901038$5387198E-A29A-41E7-A30C-8CF27B4BA3B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0833986ea89727a80d2f88b364ba4da4d1f08113","datavalue":{"value":"H\u00e4ggkvist's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901038$5CD54FB5-FF0D-4D22-84A0-7767D2ABECCF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0dfbdb0929ddc22bcd5bd1c182b95d3875d4d630","datavalue":{"value":{"entity-type":"item","numeric-id":1164054,"id":"Q1164054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901038$F38948E9-C3B4-4536-8E84-A836C5FE200A","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":"Q1901038$78EF7049-E60B-4416-8AEC-202B7A329F48","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a68f6924f4911fb107a546ad9848f55b61652de","datavalue":{"value":{"entity-type":"item","numeric-id":1844683,"id":"Q1844683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901038$AF599A47-F6C8-4B9D-A75D-4AA8ECA579ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3f92d2022f67774e7fccd1cd2348a499d5bfbd5","datavalue":{"value":{"entity-type":"item","numeric-id":4830805,"id":"Q4830805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901038$9CD1B94D-079E-4490-A0A8-1C828EAD59C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab1bacc03b81526ae4cbc517fd9658573d54e3a2","datavalue":{"value":{"entity-type":"item","numeric-id":3996285,"id":"Q3996285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901038$3387901B-5B90-417E-8604-8ACDE33F5E77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03ef46efd22e4c58a8ba7f3f8e6dd19d883363a6","datavalue":{"value":{"entity-type":"item","numeric-id":2562797,"id":"Q2562797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901038$605F4DDF-A4D6-4965-849D-44346E4BBB76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"360c9ef2553248d0ff297f6a2a3eec07611f60fa","datavalue":{"value":{"entity-type":"item","numeric-id":3953799,"id":"Q3953799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901038$3949BF47-24D5-45C4-9F8A-C7472CD1D91D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fe979badcb8bfb7a41b5de5f764eb66747617dd","datavalue":{"value":{"entity-type":"item","numeric-id":5781249,"id":"Q5781249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901038$25B4E794-6239-486E-B595-37C0A2752F70","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28e9d8d560603df1bcb123d65f1b9eb154583613","datavalue":{"value":{"entity-type":"item","numeric-id":1613467,"id":"Q1613467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6538a8230729c3721cb8ac1f2d276acd98e95539","datavalue":{"value":{"amount":"+0.8333446383476257","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":"Q1901038$EF022054-702B-464C-A8B3-37E58B59BDAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2d49473fd5d258260fcfdf22f4d2d8dcfb46e66","datavalue":{"value":{"entity-type":"item","numeric-id":1410410,"id":"Q1410410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f29157e9259175b6408c6f0eda9d8c9a3023ecde","datavalue":{"value":{"amount":"+0.8130617141723633","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":"Q1901038$4E101159-F661-4F4D-8400-760057E5C585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2834714c652b393d3bc9055ae28ac65e265b7634","datavalue":{"value":{"entity-type":"item","numeric-id":1217812,"id":"Q1217812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1160455cc1fe94e346afd7da6579c267dbbef714","datavalue":{"value":{"amount":"+0.8113617300987244","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":"Q1901038$96343E67-5B98-4BC5-BFE3-74FF2CC7590E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5311e7b2a9cfda97c3b1bdcfb57ef67a443897ce","datavalue":{"value":{"entity-type":"item","numeric-id":4372989,"id":"Q4372989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c3780389970776fd1ec3138ceeaed58eeacb505","datavalue":{"value":{"amount":"+0.8106654286384583","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":"Q1901038$7687206F-6EDA-457F-A62D-D01B54D8F455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"683f1a40aaff1183aaf2e4ea6b061663e9c6870f","datavalue":{"value":{"entity-type":"item","numeric-id":998415,"id":"Q998415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53053f2231d8456ce708f8a6daef584a0c3ed605","datavalue":{"value":{"amount":"+0.8079128265380859","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":"Q1901038$82FB899B-7FA4-46CE-9A35-4FAE9535804B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Triangle-free four-chromatic graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Triangle-free_four-chromatic_graphs"}}}}}