{"entities":{"Q1382253":{"pageid":1392993,"ns":120,"title":"Item:Q1382253","lastrevid":67304499,"modified":"2026-04-12T16:43:33Z","type":"item","id":"Q1382253","labels":{"en":{"language":"en","value":"The maximal clique and colourability of curve contact graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1133151"}},"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":"Q1382253$7E830256-49E0-41CC-9A2C-B76F09A2E999","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3377bae5a856a4ecaa175f8537875d6102993740","datavalue":{"value":{"text":"The maximal clique and colourability of curve contact graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1382253$9FA90D7A-931B-495D-9BD9-68A77F024A55","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"50b7feee2378adfd9597311656cd032c9c4a8930","datavalue":{"value":"0898.05025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382253$87ECF597-5E11-4A1C-AED5-47A37DEE9A1B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b3e1765fbec80d805ddf49a0ce44f263e29dd957","datavalue":{"value":"10.1016/S0166-218X(97)00075-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382253$95A39651-DF1C-496A-89D4-361A67C11688","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2f97addcae0de185068af846d9968c1df864cbf3","datavalue":{"value":{"entity-type":"item","numeric-id":175586,"id":"Q175586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382253$A1104E98-DDB6-4CCD-9299-411EF5255DA3","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":"Q1382253$0B71D115-228A-4381-840F-ABDCCDCE8AC1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5399645c428137aebf8ec27d073066145a6d5c40","datavalue":{"value":{"time":"+1998-03-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1382253$75650E02-60B7-407E-B031-BA013369D3DE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q1382253$28E3FFBA-B39F-4DF2-A415-0AB26B8E4097","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a492c61cb9f9c56e72706281c1d433891102534b","datavalue":{"value":"A finite set \\({\\mathcal R}\\) of curves (resp. straight line segments) in the plane is called a curve (resp. line segment) contact representation of a graph \\(H\\) if the interiors of any two curves (resp. line segments) of \\({\\mathcal R}\\) are disjoint and \\(H\\) is the intersection graph of \\({\\mathcal R}\\). The graph \\(H\\) is called the contact graph of \\({\\mathcal R}\\) and is denoted by \\(G ({\\mathcal R})\\).   This paper proves that each complete graph \\(K_n\\) has a curve and a line segment contact representation \\({\\mathcal R}\\) in which each contact point of \\({\\mathcal R}\\) has degree at most \\(k\\), where \\(k\\) is a function of \\(n\\). This paper also establishes a polynomial algorithm for finding a maximal clique in \\(H=G ({\\mathcal R})\\) and points out that the problems of finding the chromatic number and the independence number of \\(G({\\mathcal R})\\) are in general NP-complete. Some open problems are raised at the end of this paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382253$D50E2846-AEFE-4132-B55E-8E48BDD8B518","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382253$29FC53EE-CF0C-4CFF-BDBD-5E47DA9572AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382253$8F32A8B8-6121-4AF1-BB34-F9F59693082D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dd4a8c23b3bff9a76b69219a5e839ad1bdbc67a6","datavalue":{"value":"1133151","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382253$E2BDA34F-C6C9-41EF-B8FA-645ABBDF9650","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cf57a2af64e82dba585f0ddfd3928081b5afff2","datavalue":{"value":"contact graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382253$D6CE8992-C145-4F9C-834C-3B38FD6F759A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2cba1c252ffa82cbdfbe94b9b2161995fc7cef95","datavalue":{"value":"line segment contact representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382253$259AA24C-E186-4140-B5C6-05E3378A749F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382253$13F2122C-8665-4F10-ABD3-16618D186B1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2520028a283b9491b30744fc9789184f43d7b56","datavalue":{"value":"maximal clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382253$90D6C4E7-4F09-4762-B78F-9F0BEE99CA58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382253$EFED8AB4-EAEB-44B6-9603-369D915606C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b89aa1b9eed71217ebf6a719487a219071558409","datavalue":{"value":"independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382253$F9FE2697-FAA0-4682-A82E-0A3C514AED16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4ef5a98087326b7b6ae23e1778e62561b3757de","datavalue":{"value":"problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382253$BFFAF600-9238-4F5C-A52B-627CB4EE5414","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0dfbdb0929ddc22bcd5bd1c182b95d3875d4d630","datavalue":{"value":{"entity-type":"item","numeric-id":1164054,"id":"Q1164054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382253$01A3CF46-717D-4EC9-953B-70B992DC0AF4","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":"Q1382253$A03AE4D6-7827-41D7-AE1D-4EA51E16D71D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e584cb82f13d31f8a03a6c13bdb408e1c093f86","datavalue":{"value":{"entity-type":"item","numeric-id":1234300,"id":"Q1234300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382253$C23AEAF0-14C1-47B5-9534-B839BA3E9BFC","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":"Q1382253$E94357CD-9EE5-41CF-A6BF-FA10A95A0ADD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b48e325c252feaa039f03118fe31133248d503c5","datavalue":{"value":{"entity-type":"item","numeric-id":4305318,"id":"Q4305318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382253$2607BA42-37D8-408F-8DA4-3F6697B8646E","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":"Q1382253$5DEAAE77-5691-42F3-A99E-2BB5B10251D6","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":"Q1382253$DA489D3B-9BFA-4BFB-A781-54F79D9FC519","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac9a0e7ebed83e72d9b8966739b88f8b43a3f5d8","datavalue":{"value":{"entity-type":"item","numeric-id":1112845,"id":"Q1112845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382253$6E1285F5-1D62-442D-89B0-EA446735931B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ed43ffd193b725756b8b8d46ca58e4700f341bd","datavalue":{"value":{"entity-type":"item","numeric-id":1338319,"id":"Q1338319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382253$DBE434EC-79C3-4BE5-B697-62F5179E9920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6346659726f73087634abb10b71168e396896903","datavalue":{"value":{"entity-type":"item","numeric-id":1121918,"id":"Q1121918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382253$6F427784-F2C9-48F8-BF0A-BD3C1B3F5B1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85edc49e2762f78197ca674de99175269ad0218d","datavalue":{"value":{"entity-type":"item","numeric-id":3290351,"id":"Q3290351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382253$24339FFC-11DA-4530-83A5-587D706209AA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9196380ce906a8e46202e2d93cc873c08f33daa1","datavalue":{"value":"W2261837551","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382253$06A69552-9739-46A2-B6FA-A1EB012F5741","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"908f3fc5ea5bda8bed54101057493c483a1adc88","datavalue":{"value":{"entity-type":"item","numeric-id":4652597,"id":"Q4652597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f8374130dfaf06a40a68ebb7943a85223e1028c","datavalue":{"value":{"amount":"+0.9062867","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":"Q1382253$F83F9F51-7424-4F0D-8686-2DCFBDA2AC03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c9473b0f92159d642cbed27add91082c19dade9","datavalue":{"value":{"entity-type":"item","numeric-id":1791008,"id":"Q1791008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be04b29d577f3cfb081fec30dae0b5b1225f25b4","datavalue":{"value":{"amount":"+0.8940791","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":"Q1382253$BCFB3CE3-01B5-4118-88EA-D35FF57C5F73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42cafb5605f3ef60b559592a3d6cbffb027e9bef","datavalue":{"value":{"entity-type":"item","numeric-id":2712816,"id":"Q2712816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f98c1c6c2c0cbdcf73f613a490baf3432adbf07","datavalue":{"value":{"amount":"+0.87748444","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":"Q1382253$DD9CA533-85DF-46B6-9CD4-74DD75960F1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a2cf56b6f0153304c8eacc1e3c393322a148b8f","datavalue":{"value":{"entity-type":"item","numeric-id":2864287,"id":"Q2864287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aab945beee448aeee12e538c3660c31bf91c1609","datavalue":{"value":{"amount":"+0.87600744","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":"Q1382253$B5B39B34-B2E4-45C0-ACE0-5870BA821017","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7076f435c55a05eff7615b43b42f481fc2c67f4","datavalue":{"value":{"entity-type":"item","numeric-id":1412673,"id":"Q1412673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fb40cafe6b29bd605e26df6a35e766443138a4f","datavalue":{"value":{"amount":"+0.8745352","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":"Q1382253$1E2385E3-A737-45F7-9ABD-3B5C1882F94F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c076bdd181a59e5f890dbe0b57374fab0c8406b9","datavalue":{"value":{"entity-type":"item","numeric-id":4310091,"id":"Q4310091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba0d13d623580ae0bcc87b9e4ba0a73f7db90e2d","datavalue":{"value":{"amount":"+0.87445396","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":"Q1382253$1EB41ED4-D9F2-4EBF-ACC2-34F4B682A468","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b363b5f2645460ea5b43119acfe16a4f050b3773","datavalue":{"value":{"entity-type":"item","numeric-id":1696530,"id":"Q1696530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87d0cc8767b3bf041cf96238948c39d843780841","datavalue":{"value":{"amount":"+0.8737116","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":"Q1382253$6A1CD9EB-F11D-4B76-B43C-724650B46A7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb516ec0d3aac927107354a8418ce3511eae3fc0","datavalue":{"value":{"entity-type":"item","numeric-id":4279031,"id":"Q4279031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46c5e0c691581d7f3685ab5dfc5455c4afb81cd3","datavalue":{"value":{"amount":"+0.8726784","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":"Q1382253$E48C8B83-3B7E-4EE6-A20E-18132258604D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9aab812a6be3fed6b2b99247d0bc3f332161f578","datavalue":{"value":{"entity-type":"item","numeric-id":344821,"id":"Q344821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36b3f04046779b1b9c9433ac6e94a5cc56374568","datavalue":{"value":{"amount":"+0.8721916","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":"Q1382253$ED3C88F9-986B-4696-9B0A-1AAAAB241743","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccc9594b37f3bdd7128729b896b62256f1e3066d","datavalue":{"value":{"entity-type":"item","numeric-id":526243,"id":"Q526243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5903c3375e0cb39614788de74b884312ae7803f","datavalue":{"value":{"amount":"+0.8714986","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":"Q1382253$BC36E5E5-8024-4DA7-991F-1210BBDB77CA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The maximal clique and colourability of curve contact graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_maximal_clique_and_colourability_of_curve_contact_graphs"}}}}}