{"entities":{"Q1823960":{"pageid":1834702,"ns":120,"title":"Item:Q1823960","lastrevid":43348385,"modified":"2025-07-25T00:03:55Z","type":"item","id":"Q1823960","labels":{"en":{"language":"en","value":"Interval vertex-coloring of a graph with forbidden colors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4116564"}},"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":"Q1823960$0B26CBB5-FFD1-42D8-A23D-BCED08C8FEDE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ffdfb7e1c9f007d3ce2f510c4a85e1db0db6771f","datavalue":{"value":{"text":"Interval vertex-coloring of a graph with forbidden colors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1823960$35BEF1C9-CE3B-4007-9A8C-11A5DB6D046A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"24aa56483dad9a7c23c4a7f459d3eb65ea653e59","datavalue":{"value":"0682.05033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823960$558F7352-6C5B-4B32-B6F4-26F44A1E3610","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1e533db261b5c17a5dedc6d2c66a5f9fd24da5db","datavalue":{"value":"10.1016/0012-365X(89)90204-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823960$57BED332-1280-4CE9-955F-DCDF54775429","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":"Q1823960$67EAE8FA-7FF8-4FAA-8FF5-A9F0A4D182CB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1823960$47FCBD78-0647-4BD7-AD93-507E28EDA710","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"523d60a2c988cd286f4ccccecabc903d232fad30","datavalue":{"value":"The classical model of coloring the vertices of a graph with single colors so that no two adjacent vertices are colored the same is too limited to be useful in many practical applications. Therefore one must consider more general notions of graph coloring and this article is devoted to one of such generalizations.    The author considers a problem of interval coloring the vertices of a graph under the stipulation that certain colors cannot be used for some vertices. Lower and upper bounds on the minimum number of colors required for such a coloring are given. Since the general problem is NP-complete, he investigates its complexity in some special cases with a particular reference to those that can be solved by a polynomial-time algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823960$63CACC19-D25E-47BE-9DCD-0FB22E038DAC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823960$000DF3DC-FAA5-4650-ACBD-C3C6F8950FBD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"732d275ce7e75231a7b465422e3682193a2735ba","datavalue":{"value":"4116564","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823960$131DFB1D-9EC1-4CBA-AB23-519C1365ABA3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823960$522D618B-D695-4A51-991E-88EF2C72CEB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823960$12DCB448-9D6D-4AFB-A886-D16DF1A16585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"788ec43786d127bf62e1bbf0b473c43a7c87ad23","datavalue":{"value":"interval coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823960$2B92FDB1-C622-49C8-92EC-2746B15EB09E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823960$CF79BB89-3843-42F7-A262-AC7E1C21B7DC","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":"Q1823960$C4235E3C-E1BE-4A94-8A2A-529793B8A68C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823960$504F44F2-070C-42E2-9E3A-D85234DFD052","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":"Q1823960$E8782163-93C5-47DA-920D-3DA89B941512","rank":"normal"}],"P223":[{"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":"Q1823960$24E5F92F-D16F-4D23-9CEE-F775E650B77D","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":"Q1823960$9586881E-32B2-4C2A-A311-4E7AC0C76420","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":"Q1823960$1EECB483-23EB-43CB-AB8C-60031F1F7315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db4a6aa7c954c95b3d19803a097d4ad8f2debd2e","datavalue":{"value":{"entity-type":"item","numeric-id":4747511,"id":"Q4747511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823960$4228DD4D-CAFE-4205-BBC3-1554A61B4F14","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":"Q1823960$F46A4B00-94F0-477D-8AF1-0409B9FF7AD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f45afeab2013416479fec88432b03cc9d8594056","datavalue":{"value":{"entity-type":"item","numeric-id":1107984,"id":"Q1107984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823960$D3187E67-112F-4E42-8664-B38D4B714245","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89d1ac5b635610dd1c6afb481d8b9f7f0d85fa20","datavalue":{"value":{"entity-type":"item","numeric-id":3312261,"id":"Q3312261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823960$64B96C38-88DC-47BE-A134-5D9AD4551EA9","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":"Q1823960$924AAB8E-E68E-4DB7-8B93-147B7B883D49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c57671463f2fb382ce7403bc7e5e2b8df9b6d20","datavalue":{"value":{"entity-type":"item","numeric-id":4681173,"id":"Q4681173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823960$20627D0B-4DBC-446C-9FF7-45EAEC3EE6B2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97e6851e0f019b4e218256b23092c523460e5939","datavalue":{"value":{"entity-type":"item","numeric-id":1309462,"id":"Q1309462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2faaa59f00d408830c2c955d46a7197b2b14cb64","datavalue":{"value":{"amount":"+0.9657041","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":"Q1823960$2A175FE8-A641-4AC5-A700-86CDB91E9004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5d725b0a341c6654d17ea7f6b8645d2ae155440","datavalue":{"value":{"entity-type":"item","numeric-id":5883705,"id":"Q5883705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fa67df70a09ee7677e903c4cda399b055a8e23b","datavalue":{"value":{"amount":"+0.90566283","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":"Q1823960$91CA10B9-61A1-496E-A080-F663A4CB3DAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"416ab3d7b02723b78293f43863a89767ac0c0edd","datavalue":{"value":{"entity-type":"item","numeric-id":2797366,"id":"Q2797366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fb4cda20fa4cb27fe62a45b0d12edab222fc228","datavalue":{"value":{"amount":"+0.9017293","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":"Q1823960$6BAA0889-DA8E-41E5-B0B3-DCD449ACAD32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5422e0c4f1c33320a262da6254fbf9d63fc53a8a","datavalue":{"value":{"entity-type":"item","numeric-id":2182245,"id":"Q2182245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1712c7dbe91a98b93d53901f97bd2d36ee7e94ea","datavalue":{"value":{"amount":"+0.90039057","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":"Q1823960$BAE398C7-3C2C-43AA-8972-BBE7B1D5C346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6f6888483adf3996aed9d2b51382070dbd1a75e","datavalue":{"value":{"entity-type":"item","numeric-id":4645169,"id":"Q4645169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9c0df98affc50ddcbf2c4d5879c58aba7ce7d35","datavalue":{"value":{"amount":"+0.8959278","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":"Q1823960$F6C2F6BD-6CDA-4C83-941F-68EECE48FAA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d824ee8a4e25688467703a11a4a6dea8f4a52eb6","datavalue":{"value":{"entity-type":"item","numeric-id":297922,"id":"Q297922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0069c9c4dec1aae1e2f6169f4130dd97248d19d7","datavalue":{"value":{"amount":"+0.89560246","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":"Q1823960$6F88B478-24EF-4C00-B622-12B855D81011","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b33dfd30cbd1ea88b206193b8b65ee440a2bb587","datavalue":{"value":{"entity-type":"item","numeric-id":1684531,"id":"Q1684531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aef2e8f1b6c9a943f33e8f779e412b9d65d3ec9b","datavalue":{"value":{"amount":"+0.8952168","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":"Q1823960$11024E0A-961A-4237-B77E-6114F9587345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4f9c26082e5c33c333a2939884c0f2b8d3cd8f2","datavalue":{"value":{"entity-type":"item","numeric-id":4589007,"id":"Q4589007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91794b049392a7a5bebc47741870b1e5c77dfcd2","datavalue":{"value":{"amount":"+0.8933901","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":"Q1823960$4A5933D1-F174-4195-9F5E-80E8F05201E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55ac22e5cbb27d10aa3254e64405a11a59fa5cfd","datavalue":{"value":{"entity-type":"item","numeric-id":3975168,"id":"Q3975168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78a0ea54a67764ec6b2727fea8d7cc66e49dd924","datavalue":{"value":{"amount":"+0.8923142","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":"Q1823960$0152E386-7348-4F14-B5D1-DBB9114CD7AB","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":"7d9e74eea38e6b2c0a6795876e9dac6cc182df89","datavalue":{"value":{"amount":"+0.8922312","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":"Q1823960$4F16C8E1-7EB8-4698-B017-FEAD51581078","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1823960","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1823960"}}}}}