{"entities":{"Q727171":{"pageid":729020,"ns":120,"title":"Item:Q727171","lastrevid":63875652,"modified":"2026-04-11T16:08:26Z","type":"item","id":"Q727171","labels":{"en":{"language":"en","value":"Coloring non-crossing strings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6661356"}},"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":"Q727171$4DCA291D-3519-4093-B2FC-76FEA0C6CADB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6076fa0713ca62c69b17fafce0e42db95d2de969","datavalue":{"value":{"text":"Coloring non-crossing strings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q727171$9DCF962B-CB03-41C4-8D23-217AAEC284A1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5486a8d82e9e19a7cde5c96e6014fd768a57e110","datavalue":{"value":"1351.05073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q727171$E470C756-E8DE-4C4E-B18A-91CDE00B3AC5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a792bd8f0110eba3a97b8d810dfde0a08901327e","datavalue":{"value":{"entity-type":"item","numeric-id":252835,"id":"Q252835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$2EABF682-73AD-439B-BB13-F87C5D7A373E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6ef6bb5f324a8946ebbfe0f6caa4c1465fee19fb","datavalue":{"value":{"entity-type":"item","numeric-id":392030,"id":"Q392030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$BA6B43EB-27DA-423A-82F9-DF653AAB3030","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3da78518cf5fee373f1a4b61b7290c1cf383c919","datavalue":{"value":{"entity-type":"item","numeric-id":261350,"id":"Q261350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$DD616533-2D98-475C-B4E6-EC1AADEBB8D6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$9A9B8EA0-A44D-40AD-BD9A-8AF82152D46C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f5a5fb6149ff482096cebaf0b894e1861dc804b1","datavalue":{"value":{"time":"+2016-12-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q727171$5E8BCB3E-41A4-4D93-B014-E71432772A84","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2afc85d2d6b554c0cd372620107c9266e13e1646","datavalue":{"value":"https://arxiv.org/abs/1511.03827","type":"string"},"datatype":"url"},"type":"statement","id":"Q727171$A174C592-F4C5-441C-8FCB-60D025FF6061","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"ffe2c19d18025705adcefa376f791795cd20bb17","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p4","type":"string"},"datatype":"url"},"type":"statement","id":"Q727171$5C44507B-EA5F-4C40-960B-D1FAEFA0CEE3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"79e5ef419378472e5572dfd0c8baaba34a5d044f","datavalue":{"value":"Summary: For a family \\(\\mathcal{F}\\) of geometric objects in the plane, define \\(\\chi(\\mathcal{F})\\) as the least integer \\(\\ell\\) such that the elements of \\(\\mathcal{F}\\) can be colored with \\(\\ell\\) colors, in such a way that any two intersecting objects have distinct colors. When \\(\\mathcal{F}\\) is a set of pseudo-disks that may only intersect on their boundaries, and such that any point of the plane is contained in at most \\(k\\) pseudo-disks, it can be proven that \\(\\chi(\\mathcal{F})\\leq 3k/2 + o(k)\\) since the problem is equivalent to cyclic coloring of plane graphs. In this paper, we study the same problem when pseudo-disks are replaced by a family \\(\\mathcal{F}\\) of pseudo-segments (a.k.a. strings) that do not cross. In other words, any two strings of \\(\\mathcal{F}\\) are only allowed to ``touch'' each other. Such a family is said to be \\(k\\)-touching if no point of the plane is contained in more than \\(k\\) elements of \\(\\mathcal{F}\\). We give bounds on \\(\\chi(\\mathcal{F})\\) as a function of \\(k\\), and in particular we show that \\(k\\)-touching segments can be colored with \\(k+5\\) colors. This partially answers a question of \\textit{P. Hlin\u011bn\u00fd} [Discrete Appl. Math. 81, No. 1--3, 59--68 (1998; Zbl 0898.05025)] on the chromatic number of contact systems of strings.","type":"string"},"datatype":"string"},"type":"statement","id":"Q727171$9613C594-CEE0-4536-8407-E11645ABB5DF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q727171$A5ED7EE7-9C2E-4E1E-8D12-EEC7BCFB029F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7b0fa95dc2ff35fd18475d523ef8cee77e3bcb94","datavalue":{"value":"6661356","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q727171$7A232DD4-930F-4B70-94DE-95F678A30535","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q727171$DD05A6D6-15B1-4A82-8E69-BB47641D1D1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64f2a9e17c885ea89c7c49f5bd6b6ded8353be5f","datavalue":{"value":"string graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q727171$3B115488-4AD4-41EC-A4BA-E39ABD17557A","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":"Q727171$B956648E-8FD5-411B-948C-8F5C0CAA54A9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bc1a7957b7d798e1d2a9be4b818f4733f6c3027","datavalue":{"value":{"entity-type":"item","numeric-id":2439826,"id":"Q2439826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$B6B38437-9A23-4E56-9B02-844E16172EE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cee4bddc43ec049f0e7d0627723fd0c19ab3aa6","datavalue":{"value":{"entity-type":"item","numeric-id":3272975,"id":"Q3272975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$246B3EB4-1783-44EA-AF84-0FF671F04455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0d48d99a7511514ccabb7a85f71a9fe594112b6","datavalue":{"value":{"entity-type":"item","numeric-id":3679212,"id":"Q3679212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$14B31775-3936-4C90-8AEA-ADBF0F46BE7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0475b3bc7d8e0d6a05e4280fed5c43d58c678555","datavalue":{"value":{"entity-type":"item","numeric-id":5301404,"id":"Q5301404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$C78B3DFC-62DF-41FD-9749-E097E490CAB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2d1f4d5b56ef92ae4598cb2e2c639eedfdc368","datavalue":{"value":{"entity-type":"item","numeric-id":2851465,"id":"Q2851465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$2A91B39F-4BF9-455A-87EB-59CF29580AD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2efb7b91a99bf82ca0c5183eabf701dd08b3c67","datavalue":{"value":{"entity-type":"item","numeric-id":5786239,"id":"Q5786239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$D649E66B-35D0-4DB2-9BA6-7FF35167641D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"035ef14d45f13f71599bdff7a2e9bebad6c17490","datavalue":{"value":{"entity-type":"item","numeric-id":5301426,"id":"Q5301426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$6AC654CE-F629-43BB-A003-FFEEA1406853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c6b403bd691aa108dfd180d0898bdc24f7a7f28","datavalue":{"value":{"entity-type":"item","numeric-id":412277,"id":"Q412277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$4FB288A8-8EB5-4D5C-AE56-D117415DDEDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"134742456335501a6cd15e0791cd0375aeccfa51","datavalue":{"value":{"entity-type":"item","numeric-id":4328183,"id":"Q4328183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$35673B8F-2085-48A8-980A-21746737B3F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"777c9929822bbce049c733923c08710596e03c1f","datavalue":{"value":{"entity-type":"item","numeric-id":885280,"id":"Q885280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$3E71588D-7BA2-469F-82E9-E7016CCD0190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecea865227114740eed2d5859f102d9f3a0ca075","datavalue":{"value":{"entity-type":"item","numeric-id":5749319,"id":"Q5749319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$1FDA9D0E-D887-48F9-AD44-8377CA929B99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e2ea2a7f71d2c376d34542a583769554c7d6b93","datavalue":{"value":{"entity-type":"item","numeric-id":1061132,"id":"Q1061132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$D9EDB4CF-4128-4C73-A0E6-11FFDC9B3A96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2189cd480b6e1601d85beff434763b487e381914","datavalue":{"value":{"entity-type":"item","numeric-id":1382253,"id":"Q1382253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$68E4837A-9DA6-46C5-B625-E5AEAD8417E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f99ca97149e1f00db22d70fd7023a0305ace0a2","datavalue":{"value":{"entity-type":"item","numeric-id":1272471,"id":"Q1272471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$6515E765-FDBF-4881-BCC5-51E8894BA133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7fd41b0ffa9bc1b1dfebba1430a30e841f9c297","datavalue":{"value":{"entity-type":"item","numeric-id":3832590,"id":"Q3832590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$CBDA58B4-062F-4195-9E53-9F83421ECEB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3691556e169f89994b5f82e28e5fdff00d9ee0c","datavalue":{"value":{"entity-type":"item","numeric-id":1356563,"id":"Q1356563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$591EE443-CF2B-4690-A3FD-7D074040B7C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c9d2154a23ddf9691270568770d32847970edfe","datavalue":{"value":{"entity-type":"item","numeric-id":5935603,"id":"Q5935603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$75BC24A1-B209-412E-90B5-C0A96E397B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cba31ceb54ce79beec412b900f0feb6258a42783","datavalue":{"value":{"entity-type":"item","numeric-id":5591378,"id":"Q5591378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$A2B51746-8F4D-448B-88CA-2084CAFF07CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcb1437c15207124ae6619be9e6fa6befe5f1d34","datavalue":{"value":{"entity-type":"item","numeric-id":4251039,"id":"Q4251039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$D9DF98B0-F637-40D1-A8F5-C0B17CBC82A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ff6f77d40482f83e6db5befe85dc9aa15ead31f","datavalue":{"value":{"entity-type":"item","numeric-id":401487,"id":"Q401487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$656A2F30-E5C3-40CF-AAFE-FC00D70FAD3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4002661922cfbf3b51612e8c6c4804f79fd6bac7","datavalue":{"value":{"entity-type":"item","numeric-id":1850561,"id":"Q1850561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q727171$68B61645-4074-4EA9-A363-435B19F3EC44","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c64d9c39814d73232f0a4d9d61073eb707568b5b","datavalue":{"value":"bafkreihrpui2ptcn3upjbt6ncj5fdld4ieyaosmtujld5a2z3vqhgtaxru","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q727171$BC18A0C8-7010-4FE6-9090-CA92A53815CA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb86b174066baf8155fa6202a24d877ddca9fc44","datavalue":{"value":{"entity-type":"item","numeric-id":2851465,"id":"Q2851465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a79424d125f9eb00c97e6f8d5289573dc9a060db","datavalue":{"value":{"amount":"+0.8846620917320251","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":"Q727171$32158211-28FC-4B53-AA8C-93D9C921E5A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbb5f8c6dc858774a258759461b50955a80c8b62","datavalue":{"value":{"entity-type":"item","numeric-id":5348217,"id":"Q5348217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca9998736cdf45685f9100f18fa9f52b9df13fbe","datavalue":{"value":{"amount":"+0.7743846774101257","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":"Q727171$02DDE628-68C5-4ED4-836D-C011695DC880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"367c5e1fd8f25ed93ee1f3578f8c8e9b64e72ad1","datavalue":{"value":{"entity-type":"item","numeric-id":2022631,"id":"Q2022631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c13c6ad8a9fc637f98d3eed61537ba3ee25e296a","datavalue":{"value":{"amount":"+0.7635602355003357","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":"Q727171$A4D45BA7-7FB1-4C64-9117-B76A4918C672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc5cc1d9785f74982f1fed4f83920f178568c388","datavalue":{"value":{"entity-type":"item","numeric-id":3602935,"id":"Q3602935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d044978caf81c83eadb1e70cc3df02b45e8fbcf6","datavalue":{"value":{"amount":"+0.7543750405311584","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":"Q727171$3EC5BD17-1F35-420A-BB7B-BCFAC17A5A08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a1a0800e2ec64543224748a10ffec990e652b22","datavalue":{"value":{"entity-type":"item","numeric-id":412277,"id":"Q412277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c37efe8d19397d6e22b832fdf08bfbe2f825b07","datavalue":{"value":{"amount":"+0.7540024518966675","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":"Q727171$ADF43A9F-0E43-4290-835E-B35E66B3CFB2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Coloring non-crossing strings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Coloring_non-crossing_strings"}}}}}