{"entities":{"Q1844683":{"pageid":1855425,"ns":120,"title":"Item:Q1844683","lastrevid":70976709,"modified":"2026-04-13T18:38:29Z","type":"item","id":"Q1844683","labels":{"en":{"language":"en","value":"On the connection between chromatic number, maximal clique and minimal degree of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3445276"}},"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":"Q1844683$6A32868B-F89B-4223-AC34-0D60406273D2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b1fb5b6c9cd64d3c0f376574d0bb28b38d15c118","datavalue":{"value":{"text":"On the connection between chromatic number, maximal clique and minimal degree of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1844683$758B0DF4-E83F-4F82-A513-CBD9358DC18A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"028e0761298f86c217c707c1f1e1b2e87f07e7d0","datavalue":{"value":"0284.05106","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1844683$50FC8BDE-5B17-4606-9BA8-C0CCB1656E87","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cc8a5c3e0fa3ae12e198ab429bf597e6086ec58d","datavalue":{"value":"10.1016/0012-365X(74)90133-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1844683$774E98B0-DBE3-49F8-87FF-BC5910B9BD64","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1abcd6803e6a278afbcd13163730b6b71c0a896","datavalue":{"value":{"entity-type":"item","numeric-id":1844682,"id":"Q1844682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1844683$F2780938-0BA9-4245-8DD7-F5548763EDD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2798bdfe2f0de272e1cc10450dfbaa44efeb429f","datavalue":{"value":{"entity-type":"item","numeric-id":175608,"id":"Q175608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1844683$050865F8-D443-41DE-AB3E-F4A1E118ED34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb00475fd567190194461a0f087df1793eeae7c4","datavalue":{"value":{"entity-type":"item","numeric-id":6480801,"id":"Q6480801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1844683$AEE47615-336B-4321-A072-503332E34969","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":"Q1844683$C79B64ED-1495-4CB3-8F2C-4B52FA7B5AB8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"718868df62fa29cb04609217d34e1254e53a40d9","datavalue":{"value":{"time":"+1974-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1844683$BC3DD2B2-871C-4DC0-85F2-C0908180893D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aa9b55072ff7e73bf9cfc8b44a4bdff178f1ee00","datavalue":{"value":"A well known theorem due to Brooks can be stated as: For \\(r \\geq 4\\), any graph \\(G\\) has at most 2 of the following properties: (1) \\(K_r\\) is not contained in \\(G\\). (2) The chromatic number of \\(G\\) is at least \\(r\\). (3) The maximum degree of \\(G\\) is at most \\(r-1\\). In this paper the following analogue of Brooks' Theorem is proved via a sequence of lemmas: For \\(r \\geq 3\\), any graph \\(G\\) with \\(n\\) vertices has at most two of the following properties: (4) \\(K_r\\) is not contained in \\(G\\). (5) The chromatic number of \\(G\\) is at least \\(r\\). (6) The minimum degree of \\(G\\) is greater than \\(((3r-7)/(3r-4))n\\). The authors also show that if \\((3r-4)\\) divides \\(n\\), then there exists a unique graph \\(G\\) of order \\(n\\) such that (4) and (5) hold, but the minimum degree of \\(G\\) is \\(((3r-7)/(3r-4))n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1844683$42747A00-49AF-47C9-B303-82712431D173","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1844683$94829A99-4B68-4B81-A93E-AD0E2491E063","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1844683$D4AED28B-0AC6-4CD6-98C0-96408B8D749F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"65a34879e57b66bdac904f108f0e6dccdb86e0ba","datavalue":{"value":"3445276","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1844683$C74C86E6-580E-4CAA-B74E-21D538511ACB","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a11162922074f4f4b34997ec36a0bf34a479cbea","datavalue":{"value":"Q105583523","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1844683$3D18E65F-B6E0-49A8-8647-905A3DF6F248","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d3b25dc30b75558579c988a512f98264c780de85","datavalue":{"value":{"entity-type":"item","numeric-id":1171577,"id":"Q1171577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1844683$CE474CE2-FAED-4F58-A772-78CC39BA626A","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":"Q1844683$4474159E-7DBF-4FF9-8150-B3C63F18178A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5e38825a20bc1bc58f0e1282003c18527e75881","datavalue":{"value":{"entity-type":"item","numeric-id":5329579,"id":"Q5329579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1844683$B92D2F40-F566-4E0C-9399-12476854BBD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aff6a826e924293c119e44d56b266427eb1e10a2","datavalue":{"value":{"entity-type":"item","numeric-id":773996,"id":"Q773996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1844683$3DB73D11-4AC8-4BC5-B2B0-E4D9C93DFE45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa99148079d472b025dfe51f4684de4b169b6d9b","datavalue":{"value":{"entity-type":"item","numeric-id":5797166,"id":"Q5797166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1844683$A6C77EF0-63F0-45E7-8BE2-CBDED78FD1F2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b025d647ba14d010d3c02115dd3a2f6662e62392","datavalue":{"value":"https://doi.org/10.1016/0012-365x(74)90133-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1844683$D0D7BCFA-1599-420F-BCB1-AC5BCD5D6C08","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3626deaf09d72da8fcce1d88ccdbbc82e80758a3","datavalue":{"value":"W2168685161","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1844683$E9EADAB4-52B4-4B06-9508-7F2515DC289D","rank":"normal"}],"P1643":[{"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":"caeb3e09a1f5dc37ba5fb21c727a92d05210086b","datavalue":{"value":{"amount":"+0.8081759214401245","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":"Q1844683$70D578CC-6299-4BED-B71D-A8B0727EB682","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":"7a8496daa04238719479025fd1e5b3d517de2bf0","datavalue":{"value":{"amount":"+0.7927422523498535","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":"Q1844683$1A3731A2-D5CA-4470-A7F5-8A616A8C32F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"609050c1d27f21b8e49d617bd3e388805684d5ba","datavalue":{"value":{"entity-type":"item","numeric-id":3216674,"id":"Q3216674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a8ad1d401dd8ecb3b07b00b5ca58b1bd23c1049","datavalue":{"value":{"amount":"+0.7907655835151672","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":"Q1844683$FEFD3E8B-3418-4646-B5DD-EE7057D34BF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b030b715cdfc3999449beb589c6ddd8c89498441","datavalue":{"value":{"entity-type":"item","numeric-id":2822589,"id":"Q2822589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1bc326ea482008eee4402784342441242f865d7","datavalue":{"value":{"amount":"+0.7879136800765991","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":"Q1844683$5D2C6C0F-0000-4A55-95B2-BB3408627E35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f0ab67e584e9536ddc36908724845a3a5fe5fe3","datavalue":{"value":{"entity-type":"item","numeric-id":1306303,"id":"Q1306303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25c26357406a4744764b12ebba36689ced02b04f","datavalue":{"value":{"amount":"+0.7865978479385376","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":"Q1844683$83CB5753-3C93-4EE1-BEE4-08BD9D0EF64A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the connection between chromatic number, maximal clique and minimal degree of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_connection_between_chromatic_number,_maximal_clique_and_minimal_degree_of_a_graph"}}}}}