{"entities":{"Q2716522":{"pageid":2727261,"ns":120,"title":"Item:Q2716522","lastrevid":41920982,"modified":"2025-05-15T16:54:25Z","type":"item","id":"Q2716522","labels":{"en":{"language":"en","value":"On the chromatic dimension of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1599139"}},"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":"Q2716522$D8CFAA7D-FA00-4830-BF81-ED181EA4DC1D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5a1715cfff1aa336af249ff3ad87311980b5dbab","datavalue":{"value":"0977.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2716522$1AE204B2-2102-44C3-9380-76979C941B19","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8e9da64877759bbc88a07be9f6dec74cbbc48ac2","datavalue":{"value":{"entity-type":"item","numeric-id":230773,"id":"Q230773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2716522$DDBD3F31-8BDB-4DF0-AA42-B1A29BBF7286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"376e7dc3349fa03a8d8dc2066d4968146c29e639","datavalue":{"value":{"entity-type":"item","numeric-id":189953,"id":"Q189953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2716522$5F21D91F-D174-42C8-B664-71C6E8956061","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d9e418580f2b70ce6849ba62f9449722e930b0d2","datavalue":{"value":{"time":"+2002-01-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2716522$CA5CCF83-5F07-4CB2-A9EF-56CEB3C15DF3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2716522$EE232B9D-7F21-4C99-B678-F5565CCB7829","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2716522$4E353A89-8C04-4D28-A47B-B44B3B8A97DC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"00ece849cb9ac0591204c5c885f4d1c2fbae4cf4","datavalue":{"value":"1599139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2716522$0D5738EB-C4C5-43AF-9879-8AE27CD28B03","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0790746f6410ed142073636c3fdda5375d90359","datavalue":{"value":"distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q2716522$5126CA48-CBB9-4A39-BD7D-8DDB2E442110","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"729ce7d30b006e0a0feac3738fe17ebb7f491306","datavalue":{"value":"representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2716522$17189475-C876-45BB-AD4C-D136AED041B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1c5511b15959f2cf7295ca726ed02ea08c4f84f","datavalue":{"value":"basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q2716522$A2FE05F6-C822-4D90-96DE-FA7901509BA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"604cbdddca0830021cc6d38e636cc845e8de2443","datavalue":{"value":"metric dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q2716522$47357AF7-46F5-4AB0-A95E-7E6D4C1E8908","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":"Q2716522$D79A47ED-BC18-42E3-80F7-A3E505D1F2A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46b0b20ac2bcfb26f3898a0b9e5c8b569e90cf91","datavalue":{"value":{"entity-type":"item","numeric-id":2839743,"id":"Q2839743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba0271cb4dfe532bf9f57d34e45a847f38475c99","datavalue":{"value":{"amount":"+0.77708155","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":"Q2716522$910DDC2F-E61B-452A-B9F1-33C7B7CD571F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b41b23e1be0a603f1c8313d5af1ac1ea62e08aa","datavalue":{"value":{"entity-type":"item","numeric-id":890581,"id":"Q890581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e7308078feb8570187eb420a7e60c47c9e513cb","datavalue":{"value":{"amount":"+0.76572376","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":"Q2716522$5E208C47-9E97-4DBC-9433-1E3C6D28AA97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd00e8746cdc37624d91fd466c1115c2e60b8ba0","datavalue":{"value":{"entity-type":"item","numeric-id":4956444,"id":"Q4956444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3e2e9fb966db7ce75d5f12784203844f2fd1892","datavalue":{"value":{"amount":"+0.7646418","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":"Q2716522$7A1C41CA-B610-4C80-AB7D-A19B4B340DD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43bcfde16329fc8fcc800141d16460ff8a94c02a","datavalue":{"value":{"entity-type":"item","numeric-id":2999644,"id":"Q2999644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f1f4d66ab0dfaf6b090aa3086ba2e8ede72eb44","datavalue":{"value":{"amount":"+0.7589862","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":"Q2716522$97260708-51C8-4BEA-96DF-96819D364CEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85250948770875a8c2c538337661a31f56624506","datavalue":{"value":{"entity-type":"item","numeric-id":1121923,"id":"Q1121923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4621a975033855e20abf27ec24f16e396464e5f7","datavalue":{"value":{"amount":"+0.7566442","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":"Q2716522$AEFF2D33-017F-4E96-817F-B3F80A4D439E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bebb9dab0670d4ed9bf65ce53794c2dd01791d3c","datavalue":{"value":{"entity-type":"item","numeric-id":3530898,"id":"Q3530898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e9c3f081b678e463bf1653e0debae9c838e4285","datavalue":{"value":{"amount":"+0.75571036","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":"Q2716522$BA5DA988-3A1E-4855-B9DD-6CFD32A45810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff7d9429cadac749067d7fe3b2729a5a7e2f72a9","datavalue":{"value":{"entity-type":"item","numeric-id":1735142,"id":"Q1735142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ece412840a771b76c6a55be099e62281e1e80608","datavalue":{"value":{"amount":"+0.7499852","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":"Q2716522$178546F4-7207-47D0-AF28-F40D67D3BD21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54f0e6224cf536bad3f321ad7b0eb29aa40c5cd2","datavalue":{"value":{"entity-type":"item","numeric-id":5376215,"id":"Q5376215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2d107b11823c886bfe54a10ecc4b7790b2d13cc","datavalue":{"value":{"amount":"+0.74966013","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":"Q2716522$AD4A1979-7196-4CDF-B657-BC7E10BB3607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6c1297dff597a3d7abfdfd02eeba198d5268332","datavalue":{"value":{"entity-type":"item","numeric-id":1265351,"id":"Q1265351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d14b8c8aaa2f11e32cbe8db849d473e3ed9862d","datavalue":{"value":{"amount":"+0.74704266","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":"Q2716522$55553A13-3074-4028-8905-18D65002FB12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"833bc772cd7e3edad059e860a81062104f34f2ba","datavalue":{"value":{"entity-type":"item","numeric-id":283685,"id":"Q283685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc4d9d0795cae1d5f359cee34f197b3b43ea4286","datavalue":{"value":{"amount":"+0.7425837","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":"Q2716522$97C295E3-10F0-4879-84AA-213216612CA2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1248dba18de0c18ddb1630f7bde708c617991d54","datavalue":{"value":{"text":"On the chromatic dimension of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2716522$DA57D469-86A0-467D-89AC-5CF40DDC3F5B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"69d86d930ab7d15bf408652a51d91c5a2a483e7c","datavalue":{"value":{"entity-type":"item","numeric-id":6648219,"id":"Q6648219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2716522$A512C5E1-C34C-454F-8D88-5FDAD76D6E5B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4ce5619fb5c55f106419607bfd3a9fab4556d7fd","datavalue":{"value":"The concept of metric dimension of a graph introduced by \\textit{F. Harary} and \\textit{R. A. Melter} [Ars Comb. 1976, No. 2, 191-195 (1976; Zbl 0349.05118)] (also called location number by \\textit{P. J. Slater} [Proc. 6th Southeast. Conf. Comb., Graph Theor., Comput.; Boca Raton 1975, 549-559 (1975; Zbl 0316.05102)]) is studied under the name chromatic dimension. NEWLINENEWLINENEWLINEA (metric or color) basis of a graph \\(G\\) is a set of vertices \\(W\\) of minimum size such that for every pair of distinct vertices \\(u,v\\in V(G)\\) there is at least one \\(w\\in W\\) such that the length of a shortest \\(u,w\\)-path is different from the length of a shortest \\(v,w\\)-path (in other words \\(d(u,w)\\neq d(v,w)\\)). The metric (or chromatic) dimension of a graph \\(G\\), denoted by \\(\\dim(G)\\), is the size of such a basis, \\(|W|\\). It is shown that for any integer \\(k\\) there is a graph \\(G\\) with a vertex \\(v\\) whose removal changes the dimension by \\(k\\): \\(\\dim(G)-\\dim(G-v)=k\\). NEWLINENEWLINENEWLINEThe basis number of a graph \\(G\\), denoted by \\(\\text{bas}(G)\\), is the maximum value \\(r\\) such that every set of \\(r\\) vertices can be extended to a basis. Naturally, \\(\\text{bas}(G)\\leq \\dim(G)\\), with equality for complete graphs and odd cycles and it remains an open question if there are any other connected graphs for which equality holds. It is shown that \\(\\text{bas}(T)=0\\) for every tree (except \\(\\text{bas}(K_2)=1\\)), and \\(\\text{bas}(G)\\) is determined for cycles and complete multipartite graphs. Finally it is shown that if \\(0\\leq a\\leq b/2\\), then there is a graph \\(G\\) with \\(\\text{bas}(G)=a\\) and \\(\\dim(G)=b\\) and the question of whether this can be extended to all \\(0\\leq a\\leq b\\) is posed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2716522$55C2F28B-7497-4E6C-B293-F8B978E47015","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2716522","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2716522"}}}}}