{"entities":{"Q2138578":{"pageid":2149321,"ns":120,"title":"Item:Q2138578","lastrevid":57746655,"modified":"2026-04-01T06:10:02Z","type":"item","id":"Q2138578","labels":{"en":{"language":"en","value":"On the subspace choosability in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7525887"}},"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":"Q2138578$E112491E-9F68-4423-8E9B-0CBA07F3323F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d8b7dbdd0337c337a46a4d243fcaae5ebd5d88b5","datavalue":{"value":{"text":"On the subspace choosability in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2138578$A029A153-D510-4CC5-B9CC-E02D916734C8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2473a4a608b87ca8b746738298a0d3cc2fb84cb6","datavalue":{"value":"1487.05086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138578$A8BB645C-249B-4AFF-8DD6-6D89486DD0F0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"04945bdcd7e258a2e6d074a21a7d78041bf01148","datavalue":{"value":"10.37236/10765","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138578$4AE6CF99-CB6E-42EB-A0F6-5F6CC01CEF2E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fd020a3edf6c42fe8319b6c416e455df2988d288","datavalue":{"value":{"entity-type":"item","numeric-id":2119082,"id":"Q2119082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$EDFEE13F-67FD-4E22-B174-3879253B4F6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c3a50e8ff6f00f1f941a03b45dc18fe7798851c7","datavalue":{"value":{"entity-type":"item","numeric-id":1006406,"id":"Q1006406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$75D63B60-3DFC-4BC0-9C5D-99FD23C1F5A6","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":"Q2138578$DFCB1435-C23A-4848-9BCA-6A84A8A82800","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"08e3be17afd587c4497081d99b52e81a609dcb4b","datavalue":{"value":{"time":"+2022-05-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2138578$6929ACF8-C1FF-4E52-B914-3C182280D9BF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cb1e16a2fb9e1280f1c736140425492967615819","datavalue":{"value":"https://arxiv.org/abs/2110.00983","type":"string"},"datatype":"url"},"type":"statement","id":"Q2138578$68AF2423-52E6-46E2-91BD-56C7450A5FDA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"461dd194b572c5f2d8f06a3bb20e8fc1d7c957a0","datavalue":{"value":"Summary: A graph \\(G\\) is said to be \\(k\\)-subspace choosable over a field \\(F\\) if for every assignment of \\(k\\)-dimensional subspaces of some finite-dimensional vector space over \\(F\\) to the vertices of \\(G\\), it is possible to choose for each vertex a nonzero vector from its subspace so that adjacent vertices receive orthogonal vectors over \\(F\\). The subspace choice number of \\(G\\) over \\(F\\) is the smallest integer \\(k\\) for which \\(G\\) is \\(k\\)-subspace choosable over \\(F\\). This graph parameter, introduced by \\textit{G. Haynes} et al. [ibid. 17, No. 1, Research Paper R55, 18 p. (2010; Zbl 1215.05066)], is inspired by well-studied variants of the chromatic number of graphs, such as the (color) choice number and the orthogonality dimension. We study the subspace choice number of graphs over various fields. We first prove that the subspace choice number of every graph with average degree \\(d\\) is at least \\(\\Omega(\\sqrt{d/\\ln d})\\) over any field. We then focus on bipartite graphs and consider the problem of estimating, for a given integer \\(k\\), the smallest integer \\(m\\) for which the subspace choice number of the complete bipartite graph \\(K_{k, m}\\) over a field \\(F\\) exceeds \\(k\\). We prove upper and lower bounds on this quantity as well as for several extensions of this problem. Our results imply a substantial difference between the behavior of the choice number and that of the subspace choice number. We also consider the computational aspect of the subspace choice number, and show that for every \\(k \\geq 3\\) it is NP-hard to decide whether the subspace choice number of a given bipartite graph over \\(F\\) is at most \\(k\\), provided that \\(F\\) is either the real field or any finite field.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138578$A7CBDF5F-FA91-4FDC-83B0-AEC25D7BFABB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138578$7EF0928A-BB2C-44CD-8F11-883D3DB5193D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138578$F1D3AFDF-A9A2-4401-B7F8-650D7D75F693","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138578$4B09E177-D6E2-483D-B443-39E4125B7622","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"709897d6ec305a9bee59c78a0d7583a0c5dc8173","datavalue":{"value":"7525887","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138578$85096023-E631-438F-A42A-FE7DBA951668","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc481bf57f29e312ae6e17bc4a66efce8fb68b85","datavalue":{"value":"subspace choice number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138578$88ADC96B-FD0C-4963-95F8-24DA99703C85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138578$4D9020C3-DBF8-49EF-A91F-CB30889410BC","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":"Q2138578$B6381588-EF58-462E-AAC7-C140B6C86282","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"228e56440833b597a106c0b0185ad305e6f51fa4","datavalue":{"value":"W4229082471","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138578$44997C31-C776-44EF-B37B-583F986DF810","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f80aadf78dae9fc5a0138327cacf9a09e7cfa15","datavalue":{"value":{"entity-type":"item","numeric-id":3142409,"id":"Q3142409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$5AEA6731-E295-4750-864D-AC8B8933F0A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f056d9655a4ee40b006e2f06a234c0a39a59c6fd","datavalue":{"value":{"entity-type":"item","numeric-id":4500691,"id":"Q4500691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$6D024DB5-6282-4644-98D5-BC00FD0E356A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c016d05e8ae05ef746d54c202fdc70d1d765ae53","datavalue":{"value":{"entity-type":"item","numeric-id":825958,"id":"Q825958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$9715DE12-FC9E-4A26-A4E8-DC05CFD4B2E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bbaef82e8eb92dc4676d651d32794ea23b80ec1","datavalue":{"value":{"entity-type":"item","numeric-id":2798999,"id":"Q2798999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$B575F6FA-072E-46A6-A582-73F65E2BB128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dc4fb9deece1bfd0b4b5b5adadd5c35da46bd0d","datavalue":{"value":{"entity-type":"item","numeric-id":2428716,"id":"Q2428716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$0FD55C00-2C21-445A-A5B6-DE900B016A21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7b32a8240548a402659dc31549f4cbe4c44c032","datavalue":{"value":{"entity-type":"item","numeric-id":4313087,"id":"Q4313087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$44E48F33-4E51-46FC-BD9F-552501E8D8ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3573b87026595a32002fa2dc54ac8b096bc29f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3922703,"id":"Q3922703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$92847E0C-7302-40CD-99F3-4EAB9BA87361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abb42527f1c68d2b3f8593b081b99a814d33de62","datavalue":{"value":{"entity-type":"item","numeric-id":6115359,"id":"Q6115359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$43C99C30-D7BC-425D-A064-27C652C82259","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b13e3feb35c4a5abd77e6190b5cd58c6bc20fc04","datavalue":{"value":{"entity-type":"item","numeric-id":1126188,"id":"Q1126188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$803508E8-1EC4-449B-8B41-699604678145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"baf08503cfcf484cfeea97051ef21f3e0198df8d","datavalue":{"value":{"entity-type":"item","numeric-id":1025484,"id":"Q1025484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$F7CB4D57-92E0-4904-982B-C4F470D558CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f84d6cfdce72f108c696ae41269f7c042fb9fc1","datavalue":{"value":{"entity-type":"item","numeric-id":4187729,"id":"Q4187729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$C2F7A81A-621A-4A30-92B0-DBF988DBF80B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73db19c62598026ff5b94f88e4c2b0a211b66de3","datavalue":{"value":{"entity-type":"item","numeric-id":976703,"id":"Q976703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$8DE266EF-E28B-4A70-A651-7F581D48C64D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a48c289367846d2e6cbf6ff475cf182266d6c35","datavalue":{"value":{"entity-type":"item","numeric-id":4178914,"id":"Q4178914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$86764772-9A33-4419-8BD6-308407E0FCD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2aa7267fd0247f5edc723410915e6845015142","datavalue":{"value":{"entity-type":"item","numeric-id":5236381,"id":"Q5236381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$28962F02-3A84-4BB2-B989-3ADD5155294F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e0c802ff21c791501fdbaf8dba051c861e5a0ee","datavalue":{"value":{"entity-type":"item","numeric-id":2563517,"id":"Q2563517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$8D728D09-73CE-4D5A-A42A-BA3E9663A8BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b579af14f32e0ff0bb89075e11e8b6724a2a6dea","datavalue":{"value":{"entity-type":"item","numeric-id":496210,"id":"Q496210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$9A2B8D18-7948-48DA-B62E-56BDD5C228B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a744c9c17719923d1a192e9214086e46257ed20d","datavalue":{"value":{"entity-type":"item","numeric-id":1227023,"id":"Q1227023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$C0BBD899-6E35-4F3C-8ED8-E2E5AAA3FB95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08b8b9a77b27cf689aeded7f2686dca7ff8c090e","datavalue":{"value":{"entity-type":"item","numeric-id":4135588,"id":"Q4135588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$AA5FEB72-5D95-45CC-B3C9-AA91162F77C1","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"3d259e960d963b32579677d8f751872e2b402f70","datavalue":{"value":"bafkreiaqidbqyedzglrzqqji6lbfskiy6mldjkr5g3umr5qqdouwwio7ki","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138578$ABF47BA5-C397-4E92-B14F-AB287112D45D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7e904f1e1c4e0a232e69e477a1a518ff848c1cb","datavalue":{"value":{"entity-type":"item","numeric-id":3922703,"id":"Q3922703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83941f51aab65c0d3cd9310d41662e3f8b19f859","datavalue":{"value":{"amount":"+0.749840497970581","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":"Q2138578$30929A81-CE6F-42E2-B4D5-7C7A6737FA64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fd755ab2fc5ca56cc61d8a9101faab484f6f32e","datavalue":{"value":{"entity-type":"item","numeric-id":4388209,"id":"Q4388209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce68334edf302cda52b6aca97cb51d17d89e0752","datavalue":{"value":{"amount":"+0.7359879016876221","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":"Q2138578$7AFB4A51-A7EE-461C-9AA4-06D0985DBB10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d984363068dbc140516772a049f5ac6cf5566e53","datavalue":{"value":{"entity-type":"item","numeric-id":1356727,"id":"Q1356727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce68334edf302cda52b6aca97cb51d17d89e0752","datavalue":{"value":{"amount":"+0.7359879016876221","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":"Q2138578$3E6CD1A0-C42D-4913-B891-3335028913CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5332bbadbe99c1a8172a8f8e97246adb69d27cf","datavalue":{"value":{"entity-type":"item","numeric-id":4291205,"id":"Q4291205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3cdd54cca46194b732d74e1114f46c5fb2b457a","datavalue":{"value":{"amount":"+0.7241836190223694","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":"Q2138578$189A13CA-128C-4D22-A8AD-01FA866CE7FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8644d112ee079318c1130b577c37ddc1a3ad20f","datavalue":{"value":{"entity-type":"item","numeric-id":3595449,"id":"Q3595449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0fc3c79530c6a7cba047c119fb2013f30d8a7c03","datavalue":{"value":{"amount":"+0.7201346158981323","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":"Q2138578$D8CC1641-E325-4EBB-8D10-59D1D598A3D5","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138578$20393541-10D0-4B45-800F-BD1166CBB1F9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2138578","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2138578"}}}}}