{"entities":{"Q1306303":{"pageid":1317053,"ns":120,"title":"Item:Q1306303","lastrevid":46849020,"modified":"2025-12-25T17:27:22Z","type":"item","id":"Q1306303","labels":{"en":{"language":"en","value":"A strengthening of Brooks' theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1346955"}},"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":"Q1306303$3F50A987-9DC9-4D8F-BFBB-23FCD6FA6025","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b5c092ee1760883bd65c72923de3d376d1700d22","datavalue":{"value":{"text":"A strengthening of Brooks' theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1306303$D1CC651D-DBFB-4B25-898D-5E225CA5A8DE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bf368fcf4e6a647be729a7d9a569f67bbe4605ce","datavalue":{"value":"0935.05045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306303$02AFEA59-F9E3-4B75-A5DF-576030850CD1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$C1274F28-2222-423E-B8A9-F5ED573509E4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4ca1e772005d733ca22cf7d2096deaedd82034ff","datavalue":{"value":{"time":"+1999-12-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1306303$D4726AE2-AFA8-459B-80DC-65CDD38806F1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ac9a870ba38a2842c3cd0f8aceec7156d47b2d11","datavalue":{"value":"This paper mainly proves the conjecture due to \\textit{A. Beutelspacher} and \\textit{P.-R. Hering} [Ars Comb. 18, 201-216 (1984; Zbl 0554.05025)]. More precisely, the author proves that for sufficiently large \\(\\Delta\\), any graph with maximum degree at most \\(\\Delta\\) and no cliques of size \\(\\Delta\\) has a \\(\\Delta-1\\) colouring. The proof relies on the fact that if \\(G\\) is a minimal counterexample to the result, then any reasonably dense set of about \\(\\Delta\\) vertices in \\(G\\) is either a clique or the intersection of two cliques.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306303$880D2428-AC45-40C5-BD93-C198489CFD8A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306303$22776468-C3CC-40B3-A911-534F1E85D2A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306303$7BF51C64-60A1-44FB-A55B-B032A852BF32","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e22bb60738e7461074564b5f8202cba46bd349a6","datavalue":{"value":"1346955","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306303$88B737F9-86A3-48BB-B366-B1DF20A9A5A5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306303$D695799E-1C18-41FD-A7A8-D57366B9AA44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59e104fc9083dc8c4e491b340ba5128d82bfc9b1","datavalue":{"value":"colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306303$B2AA2562-9A8A-4C58-A6D8-D4CFEDB64B06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306303$AC4819E0-D024-4B92-BF75-4F10628DC8BA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d98a938c7c496671aebe9d069bbd3d70f74a635a","datavalue":{"value":{"entity-type":"item","numeric-id":661944,"id":"Q661944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$9212E5E4-19F3-4455-B83E-2B99DA5F5E65","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2a9e190796e445b79b394886bb018cccd03bd7cb","datavalue":{"value":{"entity-type":"item","numeric-id":585164,"id":"Q585164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$E5793BB2-6A1C-4017-BA95-B51DF971B69F","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":"Q1306303$1747DA02-FB23-45D0-B446-6F3FD03AD2DE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"429867d30de15d033d4b1a9341c3147b626223b9","datavalue":{"value":"https://doi.org/10.1006/jctb.1998.1891","type":"string"},"datatype":"url"},"type":"statement","id":"Q1306303$F8956D1A-3C00-4532-8085-5AD17BF32352","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9db14acb8aa096effd924a7c035ab2217df078de","datavalue":{"value":"W2011731192","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306303$800DD440-0715-438B-ABEF-3E2B0A3C4381","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4799e5a32c687eea79d573479ff8c58240f3cb62","datavalue":{"value":{"entity-type":"item","numeric-id":4004078,"id":"Q4004078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$8FD45D55-38EC-4B72-86A2-0A241010682A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f31dedd3222c00caf1fa932460b5fc7f23b1737","datavalue":{"value":{"entity-type":"item","numeric-id":2533119,"id":"Q2533119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$9B4CEB65-2DD8-47CB-AFBD-224569DDA9CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed3845c4419a791fe0022967dc28d4ee717e8c8b","datavalue":{"value":{"entity-type":"item","numeric-id":3216674,"id":"Q3216674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$6B97914D-1337-42BD-84C8-032EF5DB9221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67e393b8e79d12842759947d7f2b9beeaeff0924","datavalue":{"value":{"entity-type":"item","numeric-id":1229732,"id":"Q1229732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$9303B08A-8A2B-4B67-8ED8-9CE72705EFC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a92ab907df072bb20a1057061523b1fdda43679","datavalue":{"value":{"entity-type":"item","numeric-id":5782525,"id":"Q5782525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$55FEB4D7-8DC4-4A2B-89C9-E90E3E34882E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a59347f73363b99fbc0fc253b8806d6552a0453","datavalue":{"value":{"entity-type":"item","numeric-id":4074927,"id":"Q4074927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$D6425AD8-182A-448B-965F-75BE6903532F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f855246caf01e7d423da5ddcd02591be6660a7f0","datavalue":{"value":{"entity-type":"item","numeric-id":4857375,"id":"Q4857375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$FA4AD44F-DD28-4C42-87B4-E9E9C4D40AE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cda0a49ca0d53d97fe58d402ca2c4d240803d6b0","datavalue":{"value":{"entity-type":"item","numeric-id":3909076,"id":"Q3909076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$F06ABE44-5504-478A-AF82-3498E465CEF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83c624d0f066c67afe57801439b599cb38d0cc0c","datavalue":{"value":{"entity-type":"item","numeric-id":1354718,"id":"Q1354718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$4A0728B4-D504-497B-BDE3-CC00D2729986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a841925bd26a2accc4a3a278c045b502b9aa82f","datavalue":{"value":{"entity-type":"item","numeric-id":1297726,"id":"Q1297726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$F55DCBE5-92AE-4376-8F11-C104847C6D6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2ed1eb294bf113dae778921bdda14bdb7051703","datavalue":{"value":{"entity-type":"item","numeric-id":4250147,"id":"Q4250147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$FF5992CA-E5DC-4612-8F64-D466AA0D66A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56be0ec16de528592914ea5c274699424d38f484","datavalue":{"value":{"entity-type":"item","numeric-id":3839005,"id":"Q3839005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$6CEA8D54-C594-4A89-AF7D-08FB91C10021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e554762d0ade9d14b4023ae4280edddd5ca15768","datavalue":{"value":{"entity-type":"item","numeric-id":4242948,"id":"Q4242948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306303$8773D678-0B5C-46D3-AAE5-5BA6EFAFD83D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2f16c7ec0e61dc54ae5507a9f3e58643283d43dc","datavalue":{"value":"10.1006/JCTB.1998.1891","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306303$93F4A5D2-DEBF-494B-91E0-D380036BE68E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9fbd4366fbc952fa3d31e314b4ba9a0b40881c94","datavalue":{"value":{"entity-type":"item","numeric-id":2949718,"id":"Q2949718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95a000d293c54a0bfc73124c66b2d372ac30a260","datavalue":{"value":{"amount":"+0.8265517354011536","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":"Q1306303$7C963E52-05E1-426D-B813-019DBB4F58A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48c1ec13c1e24f95cf9fedbeda6325e51b54d9dc","datavalue":{"value":{"entity-type":"item","numeric-id":553999,"id":"Q553999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae66c596137ddd00a7bc0f80eba1e17f5aead96b","datavalue":{"value":{"amount":"+0.8147552609443665","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":"Q1306303$55A19D0A-A62C-4D4E-9A57-2E009C68EB38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"633971d66a83ec7fc674fdeace516fb42ca2761e","datavalue":{"value":{"entity-type":"item","numeric-id":2053188,"id":"Q2053188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b1ed25a0f9655426750a505c1e0d139d7c84f93","datavalue":{"value":{"amount":"+0.8109660148620605","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":"Q1306303$F89C1B8F-F858-40E4-A34A-D3D1411C13CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8307ae111639bdd9fde073e6c32f70cb6e99ded5","datavalue":{"value":{"entity-type":"item","numeric-id":5495890,"id":"Q5495890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b48815856ea0c74fb2523016ced9348cc8aa068","datavalue":{"value":{"amount":"+0.8039470911026001","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":"Q1306303$B3E98FF1-A19A-4CF3-A7A9-774EACCFF23E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4135f00646296f01947641163f30dd73e6f80b7","datavalue":{"value":{"entity-type":"item","numeric-id":4242948,"id":"Q4242948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b11221791ea6481ea15e1137bd6c669fd030bbe","datavalue":{"value":{"amount":"+0.7932314276695251","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":"Q1306303$C7A3B6B0-2C93-40B6-BB85-791135A0545F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1306303","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1306303"}}}}}