{"entities":{"Q2012896":{"pageid":2023638,"ns":120,"title":"Item:Q2012896","lastrevid":57676473,"modified":"2026-03-31T21:20:32Z","type":"item","id":"Q2012896","labels":{"en":{"language":"en","value":"The (vertex-)monochromatic index of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6756032"}},"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":"Q2012896$57704BB1-22D1-4488-A0B3-F9B7CC3EE52A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d6cd63923466cfde3b8eb67abfc4328dcf2706dd","datavalue":{"value":{"text":"The (vertex-)monochromatic index of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2012896$FFAEAC61-0220-4F77-A68C-40E3C8E62382","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bd41af899e646714ef46404a71dd467979636f9a","datavalue":{"value":"1379.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012896$997C48D7-4C33-41F4-BA7D-1DCCCF1BB9B2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0257fff2301408740f4af2dc4fcb4c7159b3e56e","datavalue":{"value":{"entity-type":"item","numeric-id":247157,"id":"Q247157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$A8480E9A-2088-4B79-AD9B-F0047D9B7EEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2bf6b57361b3180efb360b271887d95e01377385","datavalue":{"value":{"entity-type":"item","numeric-id":831023,"id":"Q831023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$FE645AD3-34F7-4AE4-8B97-87785FEA3E32","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dcf8815e3b257674fa147da7a4e7c92c91c0b3e3","datavalue":{"value":{"entity-type":"item","numeric-id":185429,"id":"Q185429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$FEB8988E-CDA5-4ECE-B334-7E5D84404A95","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4b3a2783a955645e83aada5eb39ffa5fafcd7904","datavalue":{"value":{"time":"+2017-08-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2012896$B48B1CEC-5F2A-48AE-B6BC-42629D958BE5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0b3e5ee9e7febcd6716e5ac5edc9cb0ce3a0dd47","datavalue":{"value":"https://arxiv.org/abs/1603.05338","type":"string"},"datatype":"url"},"type":"statement","id":"Q2012896$51C721B9-B63F-4631-B413-60BD0D62A0C9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7519b9bec038c474efbaad25f102023f2773dabf","datavalue":{"value":"Let \\(G\\) be an edge colored graph, let \\(k\\) be an integer such that \\(2\\leq k\\leq |V(G)|\\) and let \\(S\\) be a subset of \\(V(G)\\) of cardinality \\(k\\). A monochromatic \\(S\\)-tree is a tree that contains all vertices of \\(S\\) and all edges of \\(T\\) are of the same color. The \\(k\\)-monochromatic index \\(\\mathrm{mx}_k(G)\\) of \\(G\\) is the maximum number of colors, such that for each \\(S\\) there exists a monochromatic \\(S\\)-tree. This invariant is a generalization of monochromatic connection number \\(\\mathrm{mc}(G)\\) with the connection \\(\\mathrm{mc}(G)=\\mathrm{mx}_2(G)\\). In the first part of present work, authors prove that \\(\\mathrm{mx}_k(G)=|E(G)|-|V(G)|+2\\) for each \\(k\\geq 3\\) and any connected graph \\(G\\).  The second part is devoted to \\(k\\)-monochromatic vertex index \\(\\mathrm{mvx}_k(G)\\) of a graph \\(G\\). The difference in the definitions is that we observe vertex colored graphs and all inner vertices of a monochromatic \\(S\\)-tree have the same color. This problem is much harder as it is a NP-complete problem for every \\(k\\), \\(2\\leq k\\leq |V(G)|\\), to decide whether \\(\\mathrm{mvx}_k(G)\\geq \\ell\\) where \\(\\ell\\leq |V(G)|\\), as presented by the authors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012896$3798A24E-CD1F-44CC-ACE5-E4600C642DE4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7fbfd6a9c9db4c04ae1819627a7c5da1a84e5679","datavalue":{"value":{"entity-type":"item","numeric-id":279208,"id":"Q279208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$921DA500-49D4-4E5F-9684-D8DC8C5E5992","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012896$1EDA8A12-E490-468F-8149-E7AC55EE1777","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012896$190A1B1C-67C1-4E1F-8151-7CF971BFEE5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012896$101BDE25-6F62-4222-9EC5-6539438E11D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012896$E3C69F17-91F2-4C21-B4E8-A3FFEB8D3A18","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91c32814da3590a4f8bca59c4004c0f0e3b9d98e","datavalue":{"value":"6756032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012896$F55DA379-1271-4D14-99D4-1A4806BCBB95","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ebd51bd4a8c6756e2deec5738692fae3d581c17","datavalue":{"value":"\\(k\\)-monochromatic index","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012896$7DDEC5C6-0D8E-4FB5-AB03-7822DEF00656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9449a0af836591d52d2f87b8afc23bc5d95d1df","datavalue":{"value":"\\(k\\)-monochromatic vertex index","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012896$064C17A4-9FBF-4B0A-9879-21C9BF25B41C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5c3229079d12250eae750b84ecfb71eb6fdd70b","datavalue":{"value":"monochromatic tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012896$41FD423B-DFB3-4B42-B5FC-A0C89F273E57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50dc5a1d041f9e444212e60e5236dde69d229f7d","datavalue":{"value":"NP-complete problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012896$B9565512-777B-4609-9858-4392E33CF94B","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":"Q2012896$436CA165-F58D-4DE9-9DF4-571318A5D40E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"67be71b859560413bb31195a223e0dc922ef2130","datavalue":{"value":"W2298472417","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012896$ACA16CF9-3E15-4DE1-A31D-A23C1941E521","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$AFFECE82-71B5-4E72-9037-7738E0BF232C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4284d4e84f77300ee270e32dae45493a2dba3685","datavalue":{"value":{"entity-type":"item","numeric-id":512870,"id":"Q512870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$5035D9E6-CFAF-415C-A131-DD7511DA7FA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"534671854214d6edf2ae1cffdf97ddedc57efeca","datavalue":{"value":{"entity-type":"item","numeric-id":1752632,"id":"Q1752632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$D81484E1-BC7B-4845-B702-02DF16694E41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f19efb15b356d57240fc6db5e03866456a49cb93","datavalue":{"value":{"entity-type":"item","numeric-id":1010776,"id":"Q1010776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$4AF56CE1-8E84-483D-8DD5-BACE0C21CE07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3067c87df644a2d15a318116e9210176ec1852a","datavalue":{"value":{"entity-type":"item","numeric-id":2275401,"id":"Q2275401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$65A0F235-CD90-4ED1-89D0-551CA94411F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d00f0d21c10977bd500dd475802d6c1b1d717813","datavalue":{"value":{"entity-type":"item","numeric-id":3392716,"id":"Q3392716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$385D88C3-9FA1-4E0B-8EA2-3C953279F129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d10352eb4559425fcffdee71e895df1ba377aaed","datavalue":{"value":{"entity-type":"item","numeric-id":367076,"id":"Q367076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$7B0C4DD3-6EB4-4205-BD2B-E4C3115167D4","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":"Q2012896$43DAE151-7C41-4FB0-9442-3B561887A432","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"514f80b54f4616dde230f785b95e628fe12f7198","datavalue":{"value":{"entity-type":"item","numeric-id":1923485,"id":"Q1923485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$946D5301-4FE4-417D-BE66-8E819C1E0081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"833f7b1d3491b8a28fe6c0e6b40a73b4fecbbd5c","datavalue":{"value":{"entity-type":"item","numeric-id":5190328,"id":"Q5190328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$91F9D36F-60A1-4580-8478-83A9D132C43E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cedbeb432fce4df85d4276b8655ee4d8efacb110","datavalue":{"value":{"entity-type":"item","numeric-id":3758884,"id":"Q3758884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$3AFB1B38-865A-4A65-AA57-2BE910E780DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39955230987edbd9b04725f49e22d86a615e40b4","datavalue":{"value":{"entity-type":"item","numeric-id":3231818,"id":"Q3231818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$E6EC2D2E-6380-4E35-95A3-A4EDF2B3B1BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bea085be0c49bba666ee68f66e30bcb08a297e79","datavalue":{"value":{"entity-type":"item","numeric-id":3377651,"id":"Q3377651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012896$2EB6C49E-68B8-4374-839F-B7E8CAF64881","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e5a31f0f322010d438989e77e27bc672fa8aead5","datavalue":{"value":"10.1007/S10878-016-0048-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012896$9C332AB3-E871-4BEC-945E-5CE3FE04D4C3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b8554fe59df1ab67e8f7f0690a5633e6a15fe60","datavalue":{"value":{"entity-type":"item","numeric-id":1752632,"id":"Q1752632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7814b12a790d243d96e89a50298eedfb8cd92a81","datavalue":{"value":{"amount":"+0.7866357564926147","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":"Q2012896$E13DC060-215B-4538-90B0-6CE48887595A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23848b1c58f459dd88021586f2b2ce1b6f2f05b2","datavalue":{"value":{"entity-type":"item","numeric-id":2048994,"id":"Q2048994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a28991090fbb6d43f1df66c8e06250a6887adf14","datavalue":{"value":{"amount":"+0.7836924195289612","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":"Q2012896$53B95F93-D3D4-49A4-AF12-C16B7729566B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2b71bcc1801ae1c321ba0d2cc0ceac557482920","datavalue":{"value":{"entity-type":"item","numeric-id":2021678,"id":"Q2021678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f57d4c3b58b4dc501003927bb37cb5549a72eaaf","datavalue":{"value":{"amount":"+0.7826644778251648","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":"Q2012896$8D8259F1-4C74-4421-9EC6-D5343F9107DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cb291e6dfcb7186bfb334c4eb0808abca27f147","datavalue":{"value":{"entity-type":"item","numeric-id":3781121,"id":"Q3781121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0656721aa2dc8813a6ad5b3ac38855e951faa41b","datavalue":{"value":{"amount":"+0.772151529788971","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":"Q2012896$44F87F79-D4E8-4298-982D-53550A894AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f02cb5df6e542bcd9e3c5e670016ee7e9a75bb47","datavalue":{"value":{"entity-type":"item","numeric-id":2275401,"id":"Q2275401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8215fb24b9b64a12b1b3e28b2ee2f53b40514d4e","datavalue":{"value":{"amount":"+0.770203709602356","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":"Q2012896$8A01DDB3-859E-4FF0-98B9-A4841A38E457","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2012896","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2012896"}}}}}