{"entities":{"Q1579552":{"pageid":1590292,"ns":120,"title":"Item:Q1579552","lastrevid":43222522,"modified":"2025-07-22T12:56:49Z","type":"item","id":"Q1579552","labels":{"en":{"language":"en","value":"The complexity of \\(H\\)-colouring of bounded degree graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1506821"}},"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":"Q1579552$B23F133F-CB79-481A-B562-64AE5D34A763","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c717db26ab7628637834ee922ec97fd0b955d6cf","datavalue":{"value":{"text":"The complexity of \\(H\\)-colouring of bounded degree graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1579552$83289771-7262-4C22-B517-D746AF705858","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0cd9726bdf2b6da2c8819a3ac9fc92ccff4cca78","datavalue":{"value":"0956.05036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579552$A9720F93-C0A7-4566-BE87-3945D31083AF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6598c46e254bafe2a8551d738ed06fc406b64787","datavalue":{"value":"10.1016/S0012-365X(00)00009-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579552$D05BA883-F651-49F8-9B8A-E6F79999CE81","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"42b3be3fd84ab4e46e98f17275cc4a0c654521b5","datavalue":{"value":{"entity-type":"item","numeric-id":185365,"id":"Q185365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579552$2660CE55-7DDB-4B0E-BF40-C6C5DFFECA01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3b5375d01a59455d415f2afee9796bf93e2b3c4","datavalue":{"value":{"entity-type":"item","numeric-id":338573,"id":"Q338573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579552$53188B66-1AB7-44C9-A966-FF7A585EA85E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9380c4124a5ef272e2152da1b5d415130e3e64f8","datavalue":{"value":{"entity-type":"item","numeric-id":175596,"id":"Q175596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579552$170FA9EF-5168-412D-AE1A-86A06AF787EA","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":"Q1579552$36CA4075-964C-4427-BC05-8163E049A69D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a4ed9a44f7b8041b429a53d3f8e4cfd16b6f920e","datavalue":{"value":{"time":"+2001-03-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1579552$F6658E62-1C37-48B2-AE7E-D9C9F0C658C6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c58c9f710b3e2cc853b6d695e9ea3b5e61862816","datavalue":{"value":"Let \\(H\\) be a fixed graph; an \\(H\\)-colouring of \\(G\\) is a mapping \\(c:V(G)\\rightarrow V(H)\\) which preserves adjacency; an \\(H\\)-colouring of \\(G\\) is also called a homomorphism of \\(G\\) to \\(H\\).    In this paper the complexity of the \\(H\\)-colouring problem restricted to graphs of bounded degree is investigated. For \\(H\\)-colouring of bounded degree graphs it is pointed out that there exist polynomial algorithms for several of these restricted colouring problems. A conjecture about the complexity of certain cases of the problem is proposed, which states that for graphs of chromatic number three, all situations which are not solvable by the colouring algorithm inherent in the theorem of Brooks are NP-complete. The conjecture is motivated by proving several supporting results.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579552$5CA82887-E477-4EE0-8327-631D7C98632A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579552$73AA113D-904A-4607-AD24-B77E92DBE9DA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579552$C6B5734A-783C-4B94-A986-DFF9AEC89BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579552$4BE43B96-3256-452E-BA8C-8D9A0B9ECD17","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"845a0c343288128e9bc5058be877d46947473ce5","datavalue":{"value":"1506821","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579552$F8481705-D823-469B-B4E4-F17B9459F617","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c2c787ebfe2b5b81d414de3af465901bcdc8a28","datavalue":{"value":"\\(H\\)-colouring problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579552$CE787B5E-2FDB-4BAC-9826-341D12B35282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d4b22234c75d530f64241b56947fa988d206e61","datavalue":{"value":"Brooks theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579552$1C39CA7E-D784-40D6-AFB4-664C495B1426","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf5a8abce4d33287b10b9264b0a9350de1b354b","datavalue":{"value":"bounded degree graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579552$323969EF-9515-439B-9348-A26BB2D9AF10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579552$1AAB7689-B07F-4BEA-9A50-7FA79AD607D2","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":"Q1579552$A21B382F-3FCE-4D16-BEB5-345ECE8F8902","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4ff84faea91fb1783646933bcd77663c4b5a0b33","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00009-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1579552$B9FD9079-7B80-46A8-8E77-3B7A76CCE799","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c1a68edab4092583c2d7d43549762bddc73a5c77","datavalue":{"value":"W1988205260","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579552$81829360-4042-4E55-BDB7-96E8219F2AA6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5294193571806a3ee60a9d0dd043450fcbba6f83","datavalue":{"value":{"entity-type":"item","numeric-id":2370448,"id":"Q2370448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c06fd8d7f98ee0b47ec75c3b33d0ca21e119ee8","datavalue":{"value":{"amount":"+0.9411838","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579552$33A1E437-2A83-407E-98A2-EBC3E00D33BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b164218765f44b5ac28050552e320a4ecd77dde","datavalue":{"value":{"entity-type":"item","numeric-id":4414491,"id":"Q4414491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab12e6fcca30309f2517a1edcf4e338c217763ad","datavalue":{"value":{"amount":"+0.93290395","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579552$AAC26E5C-0439-4313-B2CB-7ED207E5E7E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aae131b8b2ba59cb8f9fe6f97ab17a8d0c89046e","datavalue":{"value":{"entity-type":"item","numeric-id":1100215,"id":"Q1100215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b5c9e0fbab33b4f316d988eaf7663dcb8d6ba3f","datavalue":{"value":{"amount":"+0.9308279","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579552$A0EDF66C-00B4-4AAA-8000-B9A11BEF3DD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d80436a7f2f690412ffc3c00684c219eb54ee6e","datavalue":{"value":{"entity-type":"item","numeric-id":3758852,"id":"Q3758852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b5c9e0fbab33b4f316d988eaf7663dcb8d6ba3f","datavalue":{"value":{"amount":"+0.9308279","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579552$5A4B84C8-DCB5-42B5-92FE-8FA7E1E69C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a005425b3d13930a466ff4bb1a3e1e416cfff82","datavalue":{"value":{"entity-type":"item","numeric-id":744083,"id":"Q744083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a3ffebcc67acc3cc48d86fe394937bfce987055","datavalue":{"value":{"amount":"+0.92409474","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579552$68D370CC-560C-45AB-8448-6AA79B94EC03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"909d85dfbaa3149a578478b867f676cf7b408ce0","datavalue":{"value":{"entity-type":"item","numeric-id":1003659,"id":"Q1003659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6e3114f84b2221342716646f122fa115f55ea21","datavalue":{"value":{"amount":"+0.9237168","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579552$8108530B-409A-4CDB-B22B-DFCF6109A955","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d36d2984c1b67ec0e6ee06ccaebdad0b82b69bc","datavalue":{"value":{"entity-type":"item","numeric-id":1045065,"id":"Q1045065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"750ba64543c2402700eb7cb67ffd6c412b14bed0","datavalue":{"value":{"amount":"+0.92345256","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579552$FAC978B4-31C9-4457-8124-A5C871070A84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a489031dcfa406b59646ef0fbd2d47ea632c824e","datavalue":{"value":{"entity-type":"item","numeric-id":4427278,"id":"Q4427278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"407dc0b43b2e96603cc0824d67124505d0952729","datavalue":{"value":{"amount":"+0.9227959","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579552$724AAD92-CB2E-4F1B-84C4-342CF5CC63DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c700f480a40d8da4ded4db169d043d8a51fea8a","datavalue":{"value":{"entity-type":"item","numeric-id":1192946,"id":"Q1192946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecbabd8312a3dd4e5d80867fa9e4a8bc4b93e751","datavalue":{"value":{"amount":"+0.92197955","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579552$BBC73CC4-26B5-412C-908D-DCFDC2F30974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eae112f0ba3fdc666a9d9f466bf913083758c944","datavalue":{"value":{"entity-type":"item","numeric-id":4668721,"id":"Q4668721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60c49075f45be00f07a41a50e70aeeaa2b727d8c","datavalue":{"value":{"amount":"+0.92193305","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579552$2CB38FE0-2C90-4F13-A086-EEFA8C21A052","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1579552","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1579552"}}}}}