{"entities":{"Q1348378":{"pageid":1359117,"ns":120,"title":"Item:Q1348378","lastrevid":67201209,"modified":"2026-04-12T16:00:14Z","type":"item","id":"Q1348378","labels":{"en":{"language":"en","value":"Complexity of list coloring problems with a fixed total number of colors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1742048"}},"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":"Q1348378$90CE7557-506A-4E1F-886E-AC321C9DFACA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4cb4dba95bc5ee1c3d9fa2b0e9d1d9d035d7ce80","datavalue":{"value":{"text":"Complexity of list coloring problems with a fixed total number of colors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1348378$48A3766A-4827-4437-A38A-D6CA4B075B93","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a8fdd1b70638442badf624edfb238113aa3db454","datavalue":{"value":"0990.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348378$1C49B7E9-AD9D-4904-AA2A-1D2F77E70B6A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"36498a8a0cb2a0fe40698a37241cfde319d61bb1","datavalue":{"value":"10.1016/S0166-218X(01)00179-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348378$0EF647EB-59E0-4280-9C4F-E35EA5E84836","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"692ce2048991e39aaf8d5623dc50cd220956e79b","datavalue":{"value":{"entity-type":"item","numeric-id":189438,"id":"Q189438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$3538003E-CAA2-4CA9-91A8-A8BF1C50F612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"61f96647728e8d9cf38c91c3045ddf65bddf2136","datavalue":{"value":{"entity-type":"item","numeric-id":183294,"id":"Q183294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$64C0686F-B4D9-4A8D-864B-91BE1C8345D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"216e7a36a8992ef42057a8f0d0dcb9de6af5f9e9","datavalue":{"value":{"entity-type":"item","numeric-id":1575602,"id":"Q1575602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$EC72AFDF-051A-48F2-9352-D1E0D6A7815D","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":"Q1348378$10A8A1A0-1BD3-4800-A399-2A605EF7328E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"227e5427b5a3bbb67302bf9b39de3184f35d2317","datavalue":{"value":{"time":"+2002-05-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1348378$CF597D33-FBC4-4231-83CD-DF4A282242B4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fd6a7cb9e2539a27bdcf01bda0b0209623bdae7f","datavalue":{"value":"In the list coloring problem, a graph \\(G=(V,E)\\) is given and with each vertex \\(v\\), a list of colors \\(L(v)\\). The problem is to select for each vertex a color from its list such that adjacent vertices get different colors. This paper looks at versions of the problem where additionally there is a function \\(p\\), such that each color \\(j\\) is given to exactly (or respectively at most) \\(p(j)\\) vertices. The paper establishes NP-completeness for the problem when there are three colors for bipartite planar graphs, and shows it is polynomially time solvable when there are two colors. The paper also shows that for a fixed number of colors, the problems (and the standard list coloring problem) are polynomially solvable for treeds and for graphs of bounded treewidth. Treeds can be defined as follows. A forest is a treed. If we have a treed and replace one vertex \\(v\\) by a treed such that each vertex in the latter treed is exactly adjacent to all neighbors of \\(v\\), then we again have a treed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1348378$C4F557EC-993A-4DDA-996B-199DD7266D28","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348378$9D13C081-BE44-4E9F-8448-74B2D7405965","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348378$39A68A14-8C13-4B3D-B4D0-AA15CB871E4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348378$48047DAA-5A85-458D-B354-C4492488B2D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348378$2DCF5951-8F40-4237-8BA7-EAB1E52A0A6B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"76988a7b965081595b17bfed5f6c627373e5a63c","datavalue":{"value":"1742048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348378$83541922-177B-4243-974C-FED425B9ECF9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1348378$8B535B0D-FAE1-45EA-8040-231ECFE0D20B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5f6aefdf1ffec3bc08d67d0b64a04330c0d9134","datavalue":{"value":"list coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1348378$D9B363FC-685C-48A6-A5CC-8982D04F93AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb8c32faca36a3d092dd867c04559c5eec1f3743","datavalue":{"value":"treed graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1348378$C72072B8-9D9A-4CFF-93CD-90AA9A372026","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eea1ea35de576c62b8101835521aa928ecd629a1","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$7EA2C955-2E74-4BC3-A5E3-F876D5F73852","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":"Q1348378$463C3139-18EB-4DB9-8F61-1B2D35DEFA2D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ec402beae0b5af1ec240175610cacba870a58d7","datavalue":{"value":{"entity-type":"item","numeric-id":1198648,"id":"Q1198648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$1CC07EE5-0CA1-40CB-9B84-EE1D2773DAF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93084df5751505b3c6a721eac731896a3039b3fc","datavalue":{"value":{"entity-type":"item","numeric-id":4291429,"id":"Q4291429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$BCDD167C-B3B3-4509-919B-7FB2B1358AB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d92b7073011bb1b4985d7d526f565ba0b3fbd9f1","datavalue":{"value":{"entity-type":"item","numeric-id":4699283,"id":"Q4699283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$9517F0F6-6B8E-4FFB-9DF4-47AAF1A9D35A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13a13bf5ea222488a462597a035d6c581000a87a","datavalue":{"value":{"entity-type":"item","numeric-id":3665151,"id":"Q3665151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$34AA4157-0E75-41CE-8DC3-A72E42A78AA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$C5EAA9B6-2102-4D33-9AA0-526589FB1413","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed91ed0176924a73cbecba9388f8a04535563e10","datavalue":{"value":{"entity-type":"item","numeric-id":4954442,"id":"Q4954442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$D84F95FB-60EB-4DBC-901A-58AE6E6EAC4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6158b50eeb07f11af0caa758cb3e8ea0fab5c43e","datavalue":{"value":{"entity-type":"item","numeric-id":2366214,"id":"Q2366214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$B2AE85CE-5677-4737-A6A1-F91E15C633EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7714ed85145f486579d3cc393927476f0211a5ba","datavalue":{"value":{"entity-type":"item","numeric-id":1296975,"id":"Q1296975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$56934E3B-FC09-49CE-AB66-0D2AC1A28DB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3573b87026595a32002fa2dc54ac8b096bc29f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3922703,"id":"Q3922703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$CFBBA328-B5E5-4E8B-857C-23A3F81E6FB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fa6d4bf66981421ea0bee1f8593bab40587b239","datavalue":{"value":{"entity-type":"item","numeric-id":1363713,"id":"Q1363713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$BBE2A1F2-A674-4C41-88EE-A3C4E2B738F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$8676ABD8-E81D-4F9D-B902-A1BE0F4E1E06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$0FCB1039-9735-46DB-8903-54D807A5667D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c63cd5f29576c98d890ea65d91adf5381d9c85d0","datavalue":{"value":{"entity-type":"item","numeric-id":1142232,"id":"Q1142232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$8A6B94AD-1C77-40BA-98C1-66489C87FE8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f636f51cbaa04d93568a9d500475b5e9a7e29330","datavalue":{"value":{"entity-type":"item","numeric-id":1363645,"id":"Q1363645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$F94D1D46-C596-4FC7-AF41-4629CA933C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"920815abd7f8c7e0d9144731327c013953758a9e","datavalue":{"value":{"entity-type":"item","numeric-id":4838453,"id":"Q4838453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$F96A6544-AECE-4412-862F-C35792F5DC65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddbe097f62791bcc42fe71dd30e6b393e0a8c6f9","datavalue":{"value":{"entity-type":"item","numeric-id":2553445,"id":"Q2553445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$85F794E3-6ACA-4AC6-B5F8-7FD550DAED01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97ca141c898326cfe034e4da2d173763055f4264","datavalue":{"value":{"entity-type":"item","numeric-id":3128916,"id":"Q3128916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$DF0F5D38-08E9-4DB8-8282-B79DF58A04FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef4754f01c6e5f4fbaf7f8521f5e41346da3c07f","datavalue":{"value":{"entity-type":"item","numeric-id":2563166,"id":"Q2563166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$69CC932B-4E06-484F-AE84-7E5E0C224038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d3de3637f427f6f65fe0eb1b99255f0f8c30657","datavalue":{"value":{"entity-type":"item","numeric-id":1356739,"id":"Q1356739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348378$E0983B9F-333A-4F6A-BD14-5F42E3842F26","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c743b9753fdf2af1e4876618befb29f70449390","datavalue":{"value":{"entity-type":"item","numeric-id":1296975,"id":"Q1296975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e10fe8389289496555c6ef7452dcb8333738182e","datavalue":{"value":{"amount":"+0.8224691152572632","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":"Q1348378$409FEF9A-939E-42B3-84AA-066DAE5D3DC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f141654b64bcc73fbcec895d0e55612bf9ae4738","datavalue":{"value":{"entity-type":"item","numeric-id":5248998,"id":"Q5248998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d720cc4af9459951e0ea326a3672f1b7dd17005","datavalue":{"value":{"amount":"+0.8224689960479736","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":"Q1348378$372EF5B3-E500-4C2D-BDF6-3472DEECEBA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eec8d18c6533e41cf9803c2ff14017327ff39c3b","datavalue":{"value":{"entity-type":"item","numeric-id":3611990,"id":"Q3611990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ad0139c37d2041c169cf4af8501225d03c4df6f","datavalue":{"value":{"amount":"+0.8208370804786682","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":"Q1348378$1CCAAAD5-3F58-4FE1-BE24-BFA11EF3D59E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2228d9b8f48eb8e83fc3854b4e98d6157c71e8bf","datavalue":{"value":{"entity-type":"item","numeric-id":4934399,"id":"Q4934399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24c9bbbea0694ca9a7ed837d882e883753b0e71e","datavalue":{"value":{"amount":"+0.8201345801353455","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":"Q1348378$6E7D4BDD-A462-4FD5-BE3F-AD3468B42D8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91c4d355d8f28fa0818357c17d306fd6ead10c48","datavalue":{"value":{"entity-type":"item","numeric-id":627124,"id":"Q627124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed6df3bcf6b9cb3374adfeaa2ce4498ba75aa55d","datavalue":{"value":{"amount":"+0.818291425704956","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":"Q1348378$1782EB11-3017-4BCF-B5D7-2583592D53DA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity of list coloring problems with a fixed total number of colors","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_of_list_coloring_problems_with_a_fixed_total_number_of_colors"}}}}}