{"entities":{"Q5936036":{"pageid":8112838,"ns":120,"title":"Item:Q5936036","lastrevid":47629924,"modified":"2026-01-02T06:34:18Z","type":"item","id":"Q5936036","labels":{"en":{"language":"en","value":"Colorings and homomorphisms of degenerate and bounded degree graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1612896"}},"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":"Q5936036$FF0EA3B9-ED15-473C-8DF4-BAD5B336DB0E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d8a628141293895a4f5ec7051a6130baf180b837","datavalue":{"value":{"text":"Colorings and homomorphisms of degenerate and bounded degree graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5936036$B542E3E0-516A-468C-ABD2-DCEE96E369CF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ac28f32ad6595c368243bbe9238644bfc7bc8548","datavalue":{"value":"0983.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936036$176A612B-F2A3-43FD-8103-0D32352584D9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"170652b609f6cf5eb674f89771010250e6b3fbd0","datavalue":{"value":"10.1016/S0012-365X(00)00245-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936036$2446AD4C-5E8D-4E81-9FE0-964E2A60733B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a112fcddf40de3e0f26627c12549da4365ccc05","datavalue":{"value":{"entity-type":"item","numeric-id":214987,"id":"Q214987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936036$407A5EFE-26C4-4C79-8273-0B6E23BCD213","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":"Q5936036$4A240C41-27BE-4E55-86A5-B70AFCD01A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0bda17b42d0bc48d46c3fc46ed0cc61c3da2f5e2","datavalue":{"value":{"entity-type":"item","numeric-id":186143,"id":"Q186143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936036$E0E8A507-E0F8-42D6-AB09-C2721A345685","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":"Q5936036$535C829D-FCB0-4444-B9DC-D366E5E92874","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2c5af00fd1fc149dba1e61ff5498f18aaaa6efa9","datavalue":{"value":{"time":"+2002-04-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5936036$4E6C3416-FC05-4785-B842-0C8B8868267A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936036$BD000325-6F1C-4456-A509-60EFBF74C753","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936036$0899511F-B134-4FAF-8E13-8D01038D84E7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ac55f8cf2115ad9da5524408e9954c29f59571ee","datavalue":{"value":"1612896","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936036$D6BEC39B-7BC5-4AED-9BD5-F2EF01E44488","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e636d6200f7544f4dd5a5bbed79f99982c70f6d","datavalue":{"value":"homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936036$0CFF5090-0A40-4EFF-A55E-60E9B23D7004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936036$A1BC0F1F-907A-4F04-9370-A13CEC2C5820","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0058e45451e14100b8e3d344c404bce66d5836c","datavalue":{"value":"degenerate graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936036$86B9E470-A205-4FD1-B5E1-87825D1DD26E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"663f171d615b457c913c22c14ba5bd660f645156","datavalue":{"value":"cubic graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936036$7D938858-C3DA-4DCA-939A-2FAA31DFA94D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936036$CA9267AE-2663-4B3B-88A2-393319453E53","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":"Q5936036$2655F0FF-5B82-4EB9-819E-DF510D65C014","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dc107d282f5b02256b9d9537344c6b499c0dd8d8","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00245-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q5936036$CEA70B06-025D-44FD-AC43-2E0472C2E10D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f9fc48b1d1e638cdcbd31daa1784f415f1c4085e","datavalue":{"value":"W2109191591","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936036$ED19FEDD-CEAE-4012-8B94-EA0D1D76854B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ff015331794144d574e05e53b37a77215af3e851","datavalue":{"value":"A graph \\(G\\) is said to have an \\(H\\)-coloring, where \\(H\\) is another graph, if there is a homomorphism of \\(G\\) into \\(H\\). It is known that the \\(H\\)-coloring problem is polynomial when \\(H\\) is bipartite and NP-complete otherwise. The famous Brooks' theorem implies that the \\(K_3\\)-coloring problem is easy for cubic graphs. It is also known that it is easy for \\(2\\)-degenerate graphs. One main result of the authors is that, for a non-bipartite triangle-free graph \\(H\\), the \\(H\\)-coloring problem is NP-complete for the class of \\(2\\)-degenerate graphs. NEWLINENEWLINENEWLINEThe \\(C_5\\)-coloring problem is known to be NP-complete for cubic graphs. Regarding the conjecture that any cubic graph with sufficiently large girth is \\(C_5\\)-colorable, the authors show that there are cubic graphs of girth \\(7\\) which are not \\(C_5\\)-colorable. They further show that it is not true that cubic graphs with sufficiently large girth are \\(C_k\\)-colorable for \\(k\\geq 11\\). As a proof technique, the authors use an ``indicator construction'' and some modifications of it.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936036$CC1ECE76-6E14-41B1-985A-367743FF68A4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"068de292421424c3d0dbafa52cc761b8d5bd08d9","datavalue":{"value":{"entity-type":"item","numeric-id":1579552,"id":"Q1579552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7748bef71a2381fd87a1254506748a050128c32","datavalue":{"value":{"amount":"+0.8185506463050842","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":"Q5936036$3C8F9CAD-6E16-49A7-914A-5D973B7E6964","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":"e7748bef71a2381fd87a1254506748a050128c32","datavalue":{"value":{"amount":"+0.8185506463050842","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":"Q5936036$7BDD12FF-5535-4EDA-9367-D6779CEBCF0E","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":"614a96d9dd98d4b236926de9c239955302727c75","datavalue":{"value":{"amount":"+0.7908635139465332","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":"Q5936036$030159D7-E352-4C2F-999A-B58213FE1423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf16b79eec26b0ba83743faa47cbf75abadc1ec0","datavalue":{"value":{"entity-type":"item","numeric-id":4925272,"id":"Q4925272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68c3b959750cdc67cd76b7457f88a5bd2fdb8658","datavalue":{"value":{"amount":"+0.7878347039222717","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":"Q5936036$D3A16B30-6F49-42DC-A850-D938993C4C43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10ab42bdb47797eb42b5d4ae7f3f67dc7dea8aed","datavalue":{"value":{"entity-type":"item","numeric-id":3826579,"id":"Q3826579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96761755a16d8609b163453ffe4f0e5fdb2a27b0","datavalue":{"value":{"amount":"+0.7870692610740662","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":"Q5936036$ED4B30C1-CB0E-48E2-B36A-419330BA3DD3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5936036","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5936036"}}}}}