{"entities":{"Q1759872":{"pageid":1770614,"ns":120,"title":"Item:Q1759872","lastrevid":70841538,"modified":"2026-04-13T17:37:33Z","type":"item","id":"Q1759872","labels":{"en":{"language":"en","value":"4-coloring \\(H\\)-free graphs when \\(H\\) is small"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6109939"}},"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":"Q1759872$548A2309-8829-46EC-83E5-23302A2AB612","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"152473d65b6507948e166e705f225d6a26a3eb0b","datavalue":{"value":{"text":"4-coloring \\(H\\)-free graphs when \\(H\\) is small","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1759872$89074A99-0E4C-4112-AB3F-44E723DED0A5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a6636eb1f256a822b877ec62370654c39e04d5eb","datavalue":{"value":"1259.05061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759872$2C683572-B37F-46E9-B91D-9CC1F8735065","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a4df628262abf79464ed4f15ac79f197844f8c4","datavalue":{"value":{"entity-type":"item","numeric-id":259036,"id":"Q259036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759872$6720BC42-F64C-40FE-8EC8-47A10BB953F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c8bda24e5db7031b811824423dc274be5147149","datavalue":{"value":{"entity-type":"item","numeric-id":170462,"id":"Q170462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759872$F04C8892-B6E3-4DCA-96E4-97E05675961C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d4eb4eef4fdf64082d7331da9350034bbb8c93e3","datavalue":{"value":{"entity-type":"item","numeric-id":417994,"id":"Q417994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759872$800EE7ED-BAD4-46D4-BAC7-AABDB7ADEA85","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759872$4E8B006C-FADF-4834-8388-10E8A2FD3473","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2f3aa46d2f66375aad8f9f235cf6aa2da570e73e","datavalue":{"value":{"time":"+2012-11-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1759872$E43BD474-EC67-4423-A650-6ADE0F966DC5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8aae6b39aab9d52d6f44f7b36ef85ed4b5020843","datavalue":{"value":"The paper determines the computational complexity of \\(4\\)-colouring \\(H\\)-free graphs where \\(H\\) is a graph on at most five vertices.  The \\(k\\)-colouring problem is to decide whether a given graph has a \\(k\\)-colouring. Here \\(k\\) is fixed, that is, it is not part of the input. The \\(k\\)-colouring problem is \\(NP\\)-complete for any fixed \\(k \\geq 3\\); however, the problem is polynomial-time solvable when restricted to certain graph classes.  A graph is said to be \\(H\\)-free if it contains no induced subgraph isomorphic to \\(H\\).      \\textit{V. V. Lozin} and \\textit{M. Kami\u0144ski} [Contrib. Discrete Math. 2, No. 1, 61--66 (2007; Zbl 1188.05065)] proved that, for \\(k \\geq 3\\), the \\(k\\)-colouring problem is \\(NP\\)-complete for the class of \\(H\\)-free graphs whenever \\(H\\) contains a cycle, while \\textit{D. Leven} and \\textit{Z. Galil} [J.\\ Algorithms 4, 35--44 (1983; Zbl 0509.68037)] proved that the same conclusion holds whenever \\(H\\) is a forest with a vertex of degree at least three. This leaves the question of the computational complexity of the \\(k\\)-colouring problem when restricted to \\(H\\)-free graphs where \\(H\\)-is a linear forest, that is, a disjoint union of paths.  Through a series of previous papers, it has been proved that, for any graph \\(H\\) on at most six vertices, the \\(3\\)-colouring problem is polynomial-time solvable on \\(H\\)-free graphs whenever \\(H\\) is a linear forest, and \\(NP\\)-complete otherwise.  In the paper under review it is proved that, for any fixed graph \\(H\\) on at most five vertices, the \\(5\\)-colouring problem is polynomial-time solvable on \\(H\\)-free graphs whenever \\(H\\) is a linear forest, and \\(NP\\)-complete otherwise.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759872$80B94058-ABA5-4E54-A719-A6E97A296077","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"540ab3dffb44ad7e0778a41442d39c1073d22f5c","datavalue":{"value":{"entity-type":"item","numeric-id":286761,"id":"Q286761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759872$A01CAF1C-5624-4F71-AE3C-8FE65BB2F498","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759872$630DAE2A-D731-4EA9-AF3B-7284D61A7AD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759872$6D74653E-461C-40AA-8F9D-622F719FF2B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759872$3646E164-C49D-4EAA-B472-C8A1C415D2A9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"076d1081ed0d070ee7116ed63aafe0fb7829687e","datavalue":{"value":"6109939","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759872$A1B59866-BA24-49F9-8A2C-760D433A79C5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759872$6CB12474-8874-4C95-A3D3-27CBDCED54AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6fac036d0386461048e4af513ab5529434c4260","datavalue":{"value":"forbidden induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759872$08D082A1-337C-4BB9-93CA-90C77D245854","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b758af885b4dc7495677bfdc55dc2e1e9a66554","datavalue":{"value":"linear forest","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759872$9020B03D-121B-4B25-B71E-478E89E48026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759872$408B901C-1B42-46AB-BDAE-FD693A67E147","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":"Q1759872$6CA5A2EE-7733-413B-9CAD-6FB24974BCC3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5b28969d32858df16de0fb7dc88b2103dd56ddba","datavalue":{"value":"https://doi.org/10.1016/j.dam.2012.08.022","type":"string"},"datatype":"url"},"type":"statement","id":"Q1759872$BC3D3101-C046-43EB-91D0-A778701737BB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1839eca41f0d41bddbea4cc40c8f0c213982ae86","datavalue":{"value":"W1565326817","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759872$24AD7870-30AD-4960-9352-E31D79594881","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a22357df9284c14a22f6c9402be1718bb0d4b82c","datavalue":{"value":"10.1016/J.DAM.2012.08.022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759872$604D13AE-E76C-44D4-BF9C-C53958C628A4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"011f840abe80ba7c8bac8bdf0105de196559ffd8","datavalue":{"value":{"entity-type":"item","numeric-id":2891376,"id":"Q2891376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98baec41e547edf2530bb4919b4cc9fc34e498e7","datavalue":{"value":{"amount":"+0.9292287","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759872$2CB092FE-11D6-416B-8B8E-1289869CDC58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b17702758061e03e4482f01b99e3f01025ca4952","datavalue":{"value":{"entity-type":"item","numeric-id":2912743,"id":"Q2912743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2766c90a2039664139c4011708bd7c44a5135bc","datavalue":{"value":{"amount":"+0.8866591","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759872$272439B0-CBAF-437E-B283-1EF1788B6BDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecbdb00c4c50ec370e450086013102ec21f79bc1","datavalue":{"value":{"entity-type":"item","numeric-id":476308,"id":"Q476308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab4f6366cd49854e97f01826a16097ae4a9898b9","datavalue":{"value":{"amount":"+0.8837302","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759872$0084218F-3495-48A7-A744-CB451D77A002","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5873cd02288c7bc556680231a71532e43c6582b0","datavalue":{"value":{"entity-type":"item","numeric-id":764301,"id":"Q764301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a961a8413968dc62d789037c01bf6490188ccd8","datavalue":{"value":{"amount":"+0.8301536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759872$12784372-3CF1-4F2C-B2D1-B1436AD9B458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4dc2bcd9ed51bfcdc0228be795bc0f370463dd70","datavalue":{"value":{"entity-type":"item","numeric-id":1739218,"id":"Q1739218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05607c2fef40874f643ec5b7c7b0b3f6db95135a","datavalue":{"value":{"amount":"+0.82828677","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759872$5365812A-FBA5-45FD-AD90-5CDD28B26F26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c9495d8d2123667e4c125696c9ad5e2826544b8","datavalue":{"value":{"entity-type":"item","numeric-id":5090995,"id":"Q5090995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e982d21941a5693af84d3dff4956f7d2e133602","datavalue":{"value":{"amount":"+0.8245667","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759872$BA395176-8D48-49A0-8F06-007A285DB3E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d5532fc5495154adad1b08303e655fe57b63cba","datavalue":{"value":{"entity-type":"item","numeric-id":3057624,"id":"Q3057624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99efebf18f054d2f583379841439e0e7ec276460","datavalue":{"value":{"amount":"+0.82329226","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759872$DEDAFE64-8F1C-477B-8FEA-96F75E2D82F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"410a9aeb3a904d44b5a7dbbde58e4a24eb92fbfd","datavalue":{"value":{"entity-type":"item","numeric-id":2182090,"id":"Q2182090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98bc42bd2642b240a1ab73a19a59473438e02d08","datavalue":{"value":{"amount":"+0.8205085","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759872$5E2E83A3-BF9F-4456-B8BF-02B3599438DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcbe3a39ab4131871a6f58ddc1dfbbbdbbcf44f3","datavalue":{"value":{"entity-type":"item","numeric-id":417995,"id":"Q417995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5aca9520093d991b26e1d62ec8ff6e751724c00","datavalue":{"value":{"amount":"+0.81767225","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759872$74021F6D-FA4F-496E-82E6-C8AFCC59BC29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"725706a45e47d34132f08d3ee5b699c84649d5a3","datavalue":{"value":{"entity-type":"item","numeric-id":5918691,"id":"Q5918691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29359fed97032decb53266089cdf3eb94b94c10c","datavalue":{"value":{"amount":"+0.81192183","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759872$7A1D226E-02BA-462B-BA9F-DEB27268EC25","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"4-coloring \\(H\\)-free graphs when \\(H\\) is small","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/4-coloring_%5C(H%5C)-free_graphs_when_%5C(H%5C)_is_small"}}}}}