{"entities":{"Q1186161":{"pageid":1196910,"ns":120,"title":"Item:Q1186161","lastrevid":69845217,"modified":"2026-04-13T10:43:55Z","type":"item","id":"Q1186161","labels":{"en":{"language":"en","value":"Some results concerning the complexity of restricted colorings of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 36292"}},"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":"Q1186161$F4684B64-3996-46C6-9D76-71049DEDFD4A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ffb8017bd53c65be8cf181a16962195b862aadcc","datavalue":{"value":{"text":"Some results concerning the complexity of restricted colorings of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1186161$9A13C06F-C806-4AD3-970B-3C0E8FADACAC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b6e66f1312cdcab78f288f85897b09fae5799fcf","datavalue":{"value":"0755.05036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186161$B9300DDE-C575-4D66-A4C2-81D681BA3454","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d598297da7fc8233fa393db302a2797820a79c43","datavalue":{"value":"10.1016/0166-218X(92)90202-L","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186161$FA23A250-EA53-43CB-AA02-1051A9DA0CC3","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":"Q1186161$970E28B1-ABB6-4855-B24A-598AF6F62D12","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1186161$2A5BF1DB-2751-4D78-A641-D7E40BE8E7AF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8a99c119721198536f5e6df0de95f3cafe464189","datavalue":{"value":"The complexity of colouring the vertices and edges of a simple graph is considered, where every vertex (or edge) has a set of zero or more forbidden colours and adjacent vertices (or edges) receive different colours. The restricted chromatic number \\(\\chi(G,F)\\) (and the chromatic index \\(\\chi'(G,F)\\), resp.) is the least \\(k\\) for which there is a restricted \\(k\\)-colouring of \\((G,F)\\). The decision problem ``Given a graph \\(G\\), a forbidding function \\(F\\) and an integer \\(k\\), is \\(\\chi(G,F)\\leq k?\\)'' is NP-complete even when restricted to bipartite graphs and \\(k=5\\). A similar result is obtained for the decision problem for edge coloured graphs. Some classes of graphs (as trees and paths) for which optimal colourings can be obtained in polynomial time are mentioned.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186161$116EDC74-FCAF-4614-8134-4968244F1D9E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186161$ED056D81-3681-4670-9C03-B42CD7F1E8F1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"895a2df36ca039737bd5fc079ff95fcae0f2df8e","datavalue":{"value":"36292","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186161$DAD68434-1918-4DDE-BFA4-8C430D110EE2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de797320ce0a2184cca07f3061d8f9daa48cc061","datavalue":{"value":"chromatic index","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186161$FE63359B-276F-431D-8A8A-9B3E5119947A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186161$90B897DC-BE3A-4CC1-93A4-0ABB12C42677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"945187689728340442f32b31bbbe2575eb5b56b3","datavalue":{"value":"restricted colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186161$3E600D7C-FF5C-4055-93B5-16D897E920BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186161$97B3F568-87FC-430E-9173-C76FFEA63E2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ab14670fd645ceec284d741b18aecb5f5131180","datavalue":{"value":"decision problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186161$E28BBFBF-BF03-4041-BDDB-63971225BDBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186161$9C4BA8FC-C928-463A-8B7A-DC507506D491","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2681750faeff29d5132b89d9392ae6736d25c7cd","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186161$518E636D-861E-4ECF-9087-62D1DE663ABB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e82f32c91e1eb0067a512f27a8cb077a4f29f958","datavalue":{"value":{"entity-type":"item","numeric-id":640843,"id":"Q640843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186161$7AB826A1-808F-4E52-940C-13E0FE23D6C3","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":"Q1186161$CDE36EA2-650C-490C-A9DB-001BB0D8FD13","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4709dc388598886bb432a7ab2082974f482f2136","datavalue":{"value":{"entity-type":"item","numeric-id":3947136,"id":"Q3947136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186161$BB0DDCCB-A45F-40BA-8153-75735F99CD6F","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":"Q1186161$5CEB59F5-8BF6-4870-8593-D5174DB535DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186161$E5275549-70DB-46D8-A4F6-1D4368DC09C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37cf1dba5ee75a1ac58208a9b9589f2d732a4181","datavalue":{"value":{"entity-type":"item","numeric-id":1838035,"id":"Q1838035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186161$843F4CFD-F61F-4AD8-A558-BABB4DAF9B97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fadc57ca78ca231627e32459401ea8bbdcdefe8","datavalue":{"value":{"entity-type":"item","numeric-id":3799842,"id":"Q3799842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186161$FF6A13E7-22F3-4A05-AA30-1C2ECDB17C17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d66ef3ae324a143c5fc1de711d33a3665d084b8f","datavalue":{"value":{"entity-type":"item","numeric-id":3205242,"id":"Q3205242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186161$E5723A79-46AD-46C4-B1F3-06D8D13E280F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186161$F03CB75C-DB94-4486-919C-3634961776BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186161$43A69BE1-9DE6-4FB4-81B4-34A0FB77E315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa153cb0fa2a4c8f83754067bec8185590f36700","datavalue":{"value":{"entity-type":"item","numeric-id":1823960,"id":"Q1823960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186161$A5E2DF9C-DC46-4636-9076-63B7AFBB9894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b088a5e2d7e73c233a78e7c077590beb3eed202","datavalue":{"value":{"entity-type":"item","numeric-id":5805003,"id":"Q5805003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186161$B2F78BC0-91EC-427A-92AE-150CD00EADAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e95153d9827fa7fa1a5472139e177ec7dbd1cd5","datavalue":{"value":{"entity-type":"item","numeric-id":3313599,"id":"Q3313599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186161$113490D6-76F3-4A1E-93F0-9C15E04DCAD1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91b1a9e0ef83650a25f470943a30eda11c06ce22","datavalue":{"value":{"entity-type":"item","numeric-id":1173977,"id":"Q1173977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cfb9ccc9e10c6eb5df8ad077d4ed0f7704b2045","datavalue":{"value":{"amount":"+0.8566055297851562","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":"Q1186161$318916C2-18B0-4356-8C49-ECD8D499D481","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54b3b5dc2d2a84f3f67044bfc541497975254f94","datavalue":{"value":{"entity-type":"item","numeric-id":1183461,"id":"Q1183461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8768f90c3c03040114a131708583f0e2fb06491","datavalue":{"value":{"amount":"+0.8489688038825989","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":"Q1186161$9E4BEE52-E5C4-4578-8166-033F465CDDC8","rank":"normal"},{"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":"99b826feb4b9e385237eabed1e0713bc2fdea27a","datavalue":{"value":{"amount":"+0.8472465872764587","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":"Q1186161$3E880C34-965B-4FD4-BD9E-196EDA71EEF7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Some results concerning the complexity of restricted colorings of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Some_results_concerning_the_complexity_of_restricted_colorings_of_graphs"}}}}}