{"entities":{"Q941403":{"pageid":943251,"ns":120,"title":"Item:Q941403","lastrevid":65575848,"modified":"2026-04-12T03:33:04Z","type":"item","id":"Q941403","labels":{"en":{"language":"en","value":"Coloring the complements of intersection graphs of geometric figures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5321331"}},"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":"Q941403$B1ECFCC1-C037-4336-9ED4-39FC0C32B07C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa28a64aea52a64aab8d33129d5a6b906bb9bc4d","datavalue":{"value":{"text":"Coloring the complements of intersection graphs of geometric figures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q941403$8DB59AA2-DAC7-43C8-A407-C675A274EE46","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2850ca570b0936f4d3ca0034d9719447be75cc0e","datavalue":{"value":"1154.05031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941403$92A9E5BC-3564-4B4A-8D7F-DAF5FEF4E81F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b48b29245211a43e7ec7c0efd3d89fdac7d83f0","datavalue":{"value":{"entity-type":"item","numeric-id":345120,"id":"Q345120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941403$DF52CBE9-3041-4C3E-A319-1C52D1EB78C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d41e1dd5efab8c5ed8ff727f6b7578f64f46360a","datavalue":{"value":{"entity-type":"item","numeric-id":318920,"id":"Q318920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941403$A0A181DD-7196-4BC5-B977-B8736ECB09EA","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":"Q941403$B3FE9ACD-22CB-4F10-BECE-BAB763FE7216","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2bf0f0ee9c49018dff9c641c5da1a78a5da873e5","datavalue":{"value":{"time":"+2008-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q941403$9A4B046D-0136-4DAD-8DB9-46B0392668F3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ddd66fb9bc9a3fe33b2cb9f29485d4178b9428bf","datavalue":{"value":"The intersection graph \\(G\\) of a family \\(\\mathcal{F}\\) of sets is the graph with vertex set \\(\\mathcal{F}\\) in which two members of \\(\\mathcal{F}\\) are adjacent if and only if they have nonempty intersection. Let \\(\\alpha(G)\\) and \\(\\gamma(G)\\) denote the size of the maximum independent set and the size of the minimum dominating set of \\(G\\), respectively. Let \\(\\chi(G)\\) denote the chromatic number of \\(G\\). Two convex bodies \\(K\\) and \\(D\\) in \\(\\mathbb{R}^n\\) are called homothetic if \\(K = x + \\lambda D\\) for a point \\(x\\) in \\(\\mathbb{R}^n\\) and some positive \\(\\lambda\\). The following results are proved in this paper.  {\\parindent=7mm \\begin{itemize}\\item[(i)]Let \\(\\overline{G}\\) be the complement of an intersection graph \\(G\\) of translations of a fixed compact convex set in the plane. Then \\(\\chi(\\overline{G}) \\leq \\min\\{3\\alpha(G)-2, 6\\gamma(G)\\}\\). The bound \\(\\chi(\\overline{G}) \\leq 6\\gamma(G)\\) is sharp.  \\item[(ii)]Let \\(\\mathbb{F}\\) be a family of translates of a convex body \\(M\\) in \\(\\mathbb{R}^n\\) for \\(n \\geq 3\\). If \\(G\\) is the intersection graph of \\(\\mathbb{F}\\), then \\(\\chi(\\overline{G}) \\leq \\left\\lceil 2(n^2-n+1)^{1/2}\\right\\rceil^{n-1} \\left\\lceil(n^2-n+1)^{1/2}\\right\\rceil(\\alpha(G)-1)+1\\).  \\item[(iii)]Let \\(\\mathcal{D}_2\\) be a family of homethetic copies of a fixed compact convex set \\(D\\) in the plane. If \\(\\overline{G}\\) is the complement of the intersection graph \\(G\\) of \\(\\mathcal{D}_2\\), then \\(\\chi(\\overline{G}) \\leq 6\\alpha(G)-5.\\)  \\end{itemize}}","type":"string"},"datatype":"string"},"type":"statement","id":"Q941403$30189A79-0E92-4DBE-861F-98350281171A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941403$66377F87-7005-4FAB-9958-3C67B151B466","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"24a660fbc1e70ec35629a91d1502afe19093b95f","datavalue":{"value":"5321331","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941403$2C88F3F9-B8BA-47D9-AF1E-0B70A0DD515F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q941403$CA675C22-787A-46D8-AAB7-FE567B69BC20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bc0d5058cf7773f67ff6548c4fa33edb07db16a","datavalue":{"value":"intersection graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q941403$FF0B0DED-3131-4424-B888-9A1836928BC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5609a50c85bfa2ac7f5fa4c3f0144026334fa5d6","datavalue":{"value":"complement","type":"string"},"datatype":"string"},"type":"statement","id":"Q941403$32567331-E006-4691-A270-78C28720A29A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5bf2c8a2779a6fd4eed47029490a3d61f5860622","datavalue":{"value":"convex set","type":"string"},"datatype":"string"},"type":"statement","id":"Q941403$183F1AB1-60F3-416A-AE3A-6E37C007BDD5","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":"Q941403$79785191-0EBF-449F-8A0A-BE05BC9501D8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"67f36d730b02ac8fd53db121f2889e5a5cf193d0","datavalue":{"value":"https://doi.org/10.1016/j.disc.2007.08.072","type":"string"},"datatype":"url"},"type":"statement","id":"Q941403$E417C91C-AA08-4149-B88B-37DA23A2FEE1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"51fcd1a9f0d69b911f5fcf419bb06676dfac07af","datavalue":{"value":"W2034130278","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941403$9CF8E2C3-8FFB-425A-8E52-73EED5625D8E","rank":"normal"}],"P223":[{"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":"Q941403$12A62FE5-913C-4891-A0D5-9C8D26E7567B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f380170dd9de5e69fb40eb46470ac085e19dc87a","datavalue":{"value":{"entity-type":"item","numeric-id":1174134,"id":"Q1174134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941403$109FE976-8E8F-4764-8E1C-87222C19C2EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cbcebd80b71e2833da2ba519ec9aae8c7792db7","datavalue":{"value":{"entity-type":"item","numeric-id":687139,"id":"Q687139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941403$BC3C78FC-AF98-4431-BDA6-A9C6F3A85FD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0a876e959b6e1cf5ba72cd222f33874a5f0081e","datavalue":{"value":{"entity-type":"item","numeric-id":1386337,"id":"Q1386337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941403$07131A74-1916-4F12-8CC5-56B95E64094C","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":"Q941403$CF1895FD-4524-458E-BCB0-6367984DAC12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b66eec2e17a45c215e8000b4defd331e6fc2c2e","datavalue":{"value":{"entity-type":"item","numeric-id":1182539,"id":"Q1182539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941403$E23B59D8-6E8C-4221-A736-03BA5C63F092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"817c9dc3bf7ac55f5d8d16c3e1697e479a60e83a","datavalue":{"value":{"entity-type":"item","numeric-id":1883668,"id":"Q1883668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941403$0DC92D39-715C-4C0B-AF20-8932DD0E9E3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f226b8e0c95041393e0319f55bf170c951b975e0","datavalue":{"value":{"entity-type":"item","numeric-id":2509292,"id":"Q2509292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941403$CDBE86DB-9165-4D26-8B8C-2E9D573374C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69faba3f97619bb706418cf382ea44fe930186cd","datavalue":{"value":{"entity-type":"item","numeric-id":4657585,"id":"Q4657585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941403$579819F9-F101-4AD0-A20C-2E5A8CA7602A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b74b281ae770a38681d471db6257ac81ed244b5","datavalue":{"value":{"entity-type":"item","numeric-id":1567625,"id":"Q1567625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941403$A8A98E19-9490-4370-A9E8-80EBC727E9F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec89088b396c12c882463c6a570d117d3ddca6ce","datavalue":{"value":{"entity-type":"item","numeric-id":4019770,"id":"Q4019770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941403$E89CE1E9-7C9E-4FFA-AD27-CA3B3823FBA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56a264fe476c72707aeeb979354f9b95d5efc662","datavalue":{"value":{"entity-type":"item","numeric-id":1868853,"id":"Q1868853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941403$CA99DA66-AF96-46AF-9052-E129CAD55778","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"613d03a93894277563e69370396cb7493eacae1b","datavalue":{"value":"10.1016/J.DISC.2007.08.072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941403$44816500-93A6-4F0A-A261-8D1A2EB10525","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61392ed04410325343d9a9e539efbd80114af3da","datavalue":{"value":{"entity-type":"item","numeric-id":4657585,"id":"Q4657585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb65f41ed96312da697a04dcede157e68ebe1691","datavalue":{"value":{"amount":"+0.9488139","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q941403$3A0FF5E3-F99B-4EB0-A0A6-E28ABFCE2D7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4a4ea1dd96c32d0afed3dced21b34288726074f","datavalue":{"value":{"entity-type":"item","numeric-id":2338577,"id":"Q2338577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"397b3a952ed7bd6cd9b92026de67994a3c7f7f7e","datavalue":{"value":{"amount":"+0.91814846","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q941403$CA59BEE6-5A93-4712-AA0F-D298C58117CA","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":"1d2123ac4892091d3eee4bb5e7fbcac218a06139","datavalue":{"value":{"amount":"+0.91592276","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q941403$518E1D74-77B1-4268-9E76-FBE7512704B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b6be50e5d54164d112251b9642e11526eaa551e","datavalue":{"value":{"entity-type":"item","numeric-id":464743,"id":"Q464743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d60b1a2b185802f04f6b3be990200431f4351e0","datavalue":{"value":{"amount":"+0.9154275","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q941403$FE01D6AF-D7E8-49BD-975B-19AF0BFB4A51","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":"5da90ae1f971b2bc4afba64245b949bdf9a6b813","datavalue":{"value":{"amount":"+0.91486937","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q941403$5FB57B12-B018-4E5C-874C-6765C5A14FFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67c978ea1a47fcadd6ee4deac37040a986096f0b","datavalue":{"value":{"entity-type":"item","numeric-id":6056781,"id":"Q6056781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e38b85e0ec67ec9b062dc843dbf05241beb4eaee","datavalue":{"value":{"amount":"+0.91425323","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q941403$353E4667-1614-4CF2-B2A4-DC3F63C9F355","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a713554cbe22b703e0350f84e3c29efe71e73fbd","datavalue":{"value":{"entity-type":"item","numeric-id":5419981,"id":"Q5419981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"282b3dc39e60792489e35d2b65d17e9e530b422a","datavalue":{"value":{"amount":"+0.91418797","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q941403$39E48590-ACBE-4593-BBC6-A186E8A49FBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"018bb94d4f8b29cc4c3edad0f1cfc68894068d1d","datavalue":{"value":{"entity-type":"item","numeric-id":2303434,"id":"Q2303434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1acab5fd183f8ae5efca512e3e838f9d762aa5a6","datavalue":{"value":{"amount":"+0.90065664","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q941403$259AD59D-045C-4139-8293-8A7CEE772BEA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Coloring the complements of intersection graphs of geometric figures","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Coloring_the_complements_of_intersection_graphs_of_geometric_figures"}}}}}