{"entities":{"Q1313876":{"pageid":1324626,"ns":120,"title":"Item:Q1313876","lastrevid":68434071,"modified":"2026-04-12T23:40:49Z","type":"item","id":"Q1313876","labels":{"en":{"language":"en","value":"The size of a minimum five-chromatic \\(K_ 4\\)-free graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 500651"}},"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":"Q1313876$27F4E7C5-2CF2-41B6-A585-27ED132E6144","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b3fe1680634366e852fd46f47c45f6b09b94c717","datavalue":{"value":{"text":"The size of a minimum five-chromatic \\(K_ 4\\)-free graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1313876$A1244EE9-D41D-44D1-895C-176A0B7F8C6A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"48c4c95fe7958db2604679c40f6d3e60f7fdd78f","datavalue":{"value":"0788.05044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313876$8AADBB5C-0311-44DA-A371-A202F14F5ADF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fb9e42e6384d91f07053b6b656503a37b41316d5","datavalue":{"value":"10.1016/0012-365X(93)90309-H","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313876$50D36071-C4B0-41DD-9D08-AFB5F9F9B98D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a63ca47176e16e5998b971c5ee94f31e4fed19d1","datavalue":{"value":{"entity-type":"item","numeric-id":930886,"id":"Q930886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313876$A898EC9D-DCB3-49A4-97AB-50F611101905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"57555e49e581043524b19e8ff224491cb25ceec4","datavalue":{"value":{"entity-type":"item","numeric-id":189757,"id":"Q189757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313876$39FB6D77-2C9C-4842-BC24-D1B5F40D7DFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a8033a256f72aacdeb797693630f8a78c7d4de5d","datavalue":{"value":{"entity-type":"item","numeric-id":1176730,"id":"Q1176730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313876$81D369DC-44A4-490B-BE39-1BEFE5C05B61","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":"Q1313876$FC1E632E-9680-4046-9A9F-92A86F523A2F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"57e9aa89b1f10c36312807a58ccd0e869aeb6e2b","datavalue":{"value":{"time":"+1994-06-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1313876$3A37B302-FEC7-4457-8014-5796D9EED419","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d0190c5f916398a36c9180e67182e0e5b7f40f2c","datavalue":{"value":"The minimum number of vertices in a five-chromatic graph that does not contain \\(K_ 4\\) is determined. \\textit{N. D. Nenov} [C. R. Acad. Bulg. Sci. 37, 301-304 (1984; Zbl 0547.05030)] has shown that the chromatic number of any ten-vertex graph without \\(K_ 4\\) is at most four. A well-known construction of Mycielski leads to the Gr\u00f6tzsch graph, an eleven- vertex, four-chromatic, triangle-free graph. Adding a new vertex adjacent to all the vertices of the Gr\u00f6tzsch graph creates a twelve-vertex, five-chromatic graph, not containing \\(K_ 4\\). Thus the minimum number of vertices in a five-chromatic, \\(K_ 4\\)-free graph is either eleven or twelve. We show that the correct answer is eleven by describing two examples.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313876$3E199F3B-8A0C-4FA5-9D5E-FE4F1C51E3C6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313876$F6D0CAD6-3651-4EF8-80E7-B5F849F727AE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"55385687f6fc2146c2a6f17a068bcad6c17814ab","datavalue":{"value":"500651","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313876$1DBD81FE-2C77-476C-AA68-EC256864D6E0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdca557614bbff8672fcfc30b394ca7fc4f0dc5a","datavalue":{"value":"five-chromatic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313876$552235C1-5299-4176-9E54-15B6B2DFCF5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313876$76F536CE-DB63-4A1F-930C-0F3AA3F1C0D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9e0e31c5e1f0e62adf3be45d6e448e1ec7b4366c","datavalue":{"value":"Gr\u00f6tzsch graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313876$4AEF38CB-7224-4386-BC68-1DBA133AA751","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":"Q1313876$DE8669BB-D0B5-4589-8116-F58533E620C8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313876$20A08931-4A65-4E4B-BABB-11667112D347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b230f12b2cf5f9568d302501bbd89dde23aacad","datavalue":{"value":{"entity-type":"item","numeric-id":4320470,"id":"Q4320470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313876$0536305B-841C-4D29-8D4D-AC5FCD9365B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5cb9d3d63301e7abf4a7efeea9fbed95fa20e75a","datavalue":{"value":{"entity-type":"item","numeric-id":3338272,"id":"Q3338272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313876$31A4508C-C6A8-460F-98B6-6B7742A87D1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7a6bf52b1c267c65bc54f52128cc0d2739175","datavalue":{"value":{"entity-type":"item","numeric-id":3035305,"id":"Q3035305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313876$E9D93C37-0476-4C50-9C57-0FC052FC8A55","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6226c8b3ede1800ad1fd8e07b3f938a92deb4ad6","datavalue":{"value":"https://doi.org/10.1016/0012-365x(93)90309-h","type":"string"},"datatype":"url"},"type":"statement","id":"Q1313876$9DED0055-420F-459B-AE68-7766FB5A1C7D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d949d5c9f951da74851971b8b3c1e94ca60e2232","datavalue":{"value":"W2043684617","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313876$38B7CCBD-B206-4E28-97D4-BA40BF851416","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba63dbed6552788a3515c264b258bd32707fb46c","datavalue":{"value":{"entity-type":"item","numeric-id":4320470,"id":"Q4320470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5af5b906e591442bca751335c33737c312ec2081","datavalue":{"value":{"amount":"+0.8505305051803589","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":"Q1313876$CF095D82-13B5-486A-8146-A276A486EB50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3adc27233fd9f375ef2312cac22a70fbcb52ef08","datavalue":{"value":{"entity-type":"item","numeric-id":1901038,"id":"Q1901038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e94826ce92c902e9d6b64abb21a87e9cc6b9d56","datavalue":{"value":{"amount":"+0.8437177538871765","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":"Q1313876$9025C905-CE34-4137-822C-19619DBB6B64","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":"371d45932d69730b0869311cae944418a9b537c1","datavalue":{"value":{"amount":"+0.8102675676345825","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":"Q1313876$708E636E-0B2C-41A0-834A-63CE41E5E540","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb6625a2442558a5d7c92123319b1373bab7d9ee","datavalue":{"value":{"entity-type":"item","numeric-id":6046762,"id":"Q6046762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0178435c31351c8139a9ea897133989629920fab","datavalue":{"value":{"amount":"+0.7846469283103943","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":"Q1313876$B61D5D88-510A-453D-B7F1-71989796B56E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb4afaea4b249b12a8fc3f670339597286675e6b","datavalue":{"value":{"entity-type":"item","numeric-id":5110643,"id":"Q5110643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01a0c781cc174448c381ea744ec3bc57b4e5d71f","datavalue":{"value":{"amount":"+0.7843614816665649","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":"Q1313876$B644F9B7-69C7-47B4-AD08-9D368F03EB6C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The size of a minimum five-chromatic \\(K 4\\)-free graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_size_of_a_minimum_five-chromatic_%5C(K_4%5C)-free_graph"}}}}}