{"entities":{"Q1767668":{"pageid":1778410,"ns":120,"title":"Item:Q1767668","lastrevid":48430468,"modified":"2026-01-04T19:02:57Z","type":"item","id":"Q1767668","labels":{"en":{"language":"en","value":"(\\(\\Delta-k\\))-critical graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2142247"}},"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":"Q1767668$425F9182-2139-4F10-9852-C7EA33161B16","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"48aec2061d7ea45804088b0f618be6d90a536ef2","datavalue":{"value":{"text":"(\\(\\Delta-k\\))-critical graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1767668$A7DCEA49-CC1E-4B57-8D34-D8A6D012A014","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ea53debc0b5b792bee178cf43368e31d8e2923b2","datavalue":{"value":"1062.05056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767668$A5F33589-B033-42D0-ABFE-EBF5DA4DB6EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"924ad6a6eef0f878f8b47d4a95f2ad668f735644","datavalue":{"value":{"entity-type":"item","numeric-id":324853,"id":"Q324853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767668$C32C0AE5-FA2A-4EBF-A231-676256E75AC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7ffb806c5719dc12f172350c3d64b60f5672ed8c","datavalue":{"value":{"entity-type":"item","numeric-id":215097,"id":"Q215097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767668$BFAA102D-CC3D-46C1-B6F7-08FADB65B754","rank":"normal"},{"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":"Q1767668$B6AA8D1C-1268-4FD8-9202-5A349D9DEEC2","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":"Q1767668$AA177DE9-0AEC-40D9-BC48-2A9ACD91B56B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bd47d06c0da02a3275cef5e1a053a13d04438c27","datavalue":{"value":{"time":"+2005-03-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1767668$7B65B4D3-60E0-4648-BADA-A18A77EDAB2C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2f8a5cefea9bd03104fcc77816da47b862d5c11a","datavalue":{"value":"The paper contains a characterisation of \\((\\Delta-2),(\\Delta-3), (\\Delta-4)\\) and \\((\\Delta-5)\\)-colourable graphs for a sufficiently large value of \\(\\Delta\\) (where \\(\\Delta\\) is the maximum degree of a graph). These results extend a classical result of \\textit{R. L. Brooks} [Proc. Camb. Philos. Soc. 37, 194--197 (1941; Zbl 0027.26403)] on \\(\\Delta\\) and \\(\\Delta+1\\)-colourable graphs and a characterisation of \\(\\Delta-1\\)-colourable graphs by \\textit{B. Reed} [J. Comb. Theory, Ser. B 76, 136--149 (1999; Zbl 0935.05045)]. Moreover a linear time algorithm for checking the \\((\\Delta-k)\\)-colourability, for sufficiently large \\(\\Delta\\) and any constant \\(k\\), is provided.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767668$1777349F-E2F5-4C81-8130-C0CE4AC56BC1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767668$BB0D0779-8DF9-49E9-800A-546F0F7EA0B1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"640f3015bb1c7954c69cc3ccb061b61b2056ed4a","datavalue":{"value":"2142247","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767668$D42B87AD-4485-4730-AE50-51A9BA553634","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54145a1c4a82b2f7b1704c92ef20f7093307c734","datavalue":{"value":"critical graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767668$D0147004-B4D6-4FED-A7D6-B2BD69EDDF7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59e104fc9083dc8c4e491b340ba5128d82bfc9b1","datavalue":{"value":"colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767668$0A62E9EA-95EF-4BF7-81D6-EC14544D69DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e940ac37279303889e6f8c6cd8870094f89fb3aa","datavalue":{"value":"probabilistic method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767668$CAE2E28F-46D4-486F-B4BD-E95B744B65C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767668$D5D509DA-84FC-4BF5-8773-3C73D51F9BC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13196c9c8a3f396e97e9426bc7763f437026aa4b","datavalue":{"value":"maximum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767668$4E7FA297-C0A5-4711-B3E6-A5D567F2E089","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af45ac16b5c3b4cb5ad35340a1e807846a86d0e0","datavalue":{"value":{"entity-type":"item","numeric-id":593274,"id":"Q593274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767668$DB620F48-B220-46F3-8173-C45549BA3BAB","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":"Q1767668$B0AD961C-7AFD-48E9-8D2F-C63DE280C3E4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b719650447183e89b2fee45de015eec2c0f9f4db","datavalue":{"value":"https://doi.org/10.1016/j.jctb.2004.09.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q1767668$B2A21248-69E9-49FB-8E0B-01A9D1675453","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"62f59edad71fbcb91b8993041d0b8bece6c3356b","datavalue":{"value":"W1968677127","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767668$93D3F273-4B6B-4D48-A675-1CBEC40EEC36","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"306906c3685744871da96dd98138be622dd9df66","datavalue":{"value":{"entity-type":"item","numeric-id":4238167,"id":"Q4238167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767668$7125E90A-BBA6-4F50-8221-97DECDB7BC54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4d4fb0d146535ef37cc221544e998161ff87740","datavalue":{"value":{"entity-type":"item","numeric-id":5520564,"id":"Q5520564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767668$F67B24B4-524D-4065-9D10-D851EE07ADF9","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":"Q1767668$86ABAD34-AD18-4386-94FB-AD58B218C92B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35184f581a4fa42ee779b59d5e27eea0c204219f","datavalue":{"value":{"entity-type":"item","numeric-id":5931450,"id":"Q5931450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767668$DD505057-88E1-42D6-A1CC-48D4CBCCA2A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f40c014091ed916837cda894504d72ff91794b08","datavalue":{"value":{"entity-type":"item","numeric-id":4261186,"id":"Q4261186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767668$8B0F3C16-2919-4999-B720-D7858A30DED5","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":"Q1767668$DA092EEE-F755-45E3-A8E0-2EBAFE0414DE","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":"Q1767668$0A11B1FE-4B09-4F5B-A2BD-C2296467D1EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55ae28322679b63ea89547660e6db668af18c547","datavalue":{"value":{"entity-type":"item","numeric-id":5176002,"id":"Q5176002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767668$55BA89A6-959B-4D4E-BF6B-975F3B4137F1","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":"Q1767668$2F874971-A991-4A42-8F7E-3AC1A9D7B9B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f0f05102d1acb49e70d449d1ebac6d1f45297ef","datavalue":{"value":{"entity-type":"item","numeric-id":1306303,"id":"Q1306303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767668$D354513E-CC64-42DB-A468-D170803E4920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"779f2ad12863a733bf0d284d9407a8b122f663eb","datavalue":{"value":{"entity-type":"item","numeric-id":759160,"id":"Q759160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767668$B03D8B58-2BE7-429A-BF8B-C849D21D2CE3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e8d35c5b7e0d623e9ab1570d1fa67d1771e3b0d4","datavalue":{"value":"10.1016/J.JCTB.2004.09.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767668$0FBEFF33-6E98-467C-87FA-C1833FF1A279","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35e32b11b213ffec5502dcc3849af32d46b0870a","datavalue":{"value":{"entity-type":"item","numeric-id":462929,"id":"Q462929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0c0243c765a6927f78c81a765341c11d7fb2fc7","datavalue":{"value":{"amount":"+0.8294919729232788","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":"Q1767668$570DE12C-7C85-4005-85F0-B973687FD201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15c7aab9e4b1fd4b1bde591966f577d18d5b4c31","datavalue":{"value":{"entity-type":"item","numeric-id":3839005,"id":"Q3839005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"983f3a645ae75b5d53bd5d0b310c3e75b1e4fac2","datavalue":{"value":{"amount":"+0.800599217414856","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":"Q1767668$EFDE293A-40EE-4539-B5FE-2B7ED6B93356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91d6a0730c24f5aba767a686a67ffd8ce849cc4e","datavalue":{"value":{"entity-type":"item","numeric-id":2768312,"id":"Q2768312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5251dac59a62f3e791f6389463720f4ea832c153","datavalue":{"value":{"amount":"+0.7937905192375183","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":"Q1767668$70B4633C-B6E2-4637-81B9-EAEAB6E7660A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab5d4c673c54a1b9ff7da97bd9acd2e9e7c194de","datavalue":{"value":{"entity-type":"item","numeric-id":844167,"id":"Q844167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5251dac59a62f3e791f6389463720f4ea832c153","datavalue":{"value":{"amount":"+0.7937905192375183","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":"Q1767668$37EE9659-9DF5-4731-8E0C-1EDB7700920C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85a71e30a1dc383ab4f851375f76517a20c44f52","datavalue":{"value":{"entity-type":"item","numeric-id":3046497,"id":"Q3046497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56e242e6aecce560f946d2ad81ecfe89fd8a3393","datavalue":{"value":{"amount":"+0.7915463447570801","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":"Q1767668$BE7B340E-49AD-4798-995B-94EE872CAD75","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1767668","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1767668"}}}}}