{"entities":{"Q1383364":{"pageid":1394104,"ns":120,"title":"Item:Q1383364","lastrevid":70296561,"modified":"2026-04-13T13:49:13Z","type":"item","id":"Q1383364","labels":{"en":{"language":"en","value":"\\(T\\)-choosability in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1139428"}},"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":"Q1383364$47974396-61A3-497F-A614-DA12E65A60D2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f3214ce68f75781ad498e75f0f58c2130a58ebfe","datavalue":{"value":{"text":"\\(T\\)-choosability in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1383364$43DAC995-70F1-442C-BDFA-358CAE2332A3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d83916379308b2c2694c6a1c13bb25dcc21ea1a9","datavalue":{"value":"0890.05026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1383364$161202BD-F30E-42A3-9662-8289C390DD73","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"792f1026a0e8f901a76e4ff8ceee7763a55c7b8e","datavalue":{"value":"10.1016/S0166-218X(97)00124-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1383364$3FA75E45-8FC7-4239-9C46-C70CDEC9B8D1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1383364$EACC3CB0-9902-4AEC-9F61-C571AE1AA7F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f4b9e7445f95004115eb89fe7d9b6336f6506b1f","datavalue":{"value":{"entity-type":"item","numeric-id":1268730,"id":"Q1268730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1383364$A2458FC3-EEF5-490A-A678-5D6237537960","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":"Q1383364$75E176D2-0842-44E6-8AD2-9EFD146F85DF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a81481511537480aa6e4dec18faa040d3b5b45d6","datavalue":{"value":{"time":"+1998-06-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1383364$610395E4-E5F3-4956-BE5C-39003BB50F1A","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":"Q1383364$11303649-A745-4927-BC6E-0546CC1C48FE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1a18406f41cb4e108f1aee02f95e9a80afb6e075","datavalue":{"value":"Given a set of nonnegative integers \\(T\\) and a function \\(S\\) which assigns a set of integers \\(S(v)\\) to each vertex \\(v\\) of a graph \\(G\\), an \\(S\\)-list \\(T\\)-coloring \\(c\\) of \\(G\\) is a vertex-coloring (with positive integers) of \\(G\\) such that \\(c(v)\\in S(v)\\) whenever \\(v\\in V(G)\\) and \\(|c(u)-c(w)|\\notin T\\) whenever \\(uw\\in E(G)\\). For a fixed \\(T\\), the \\(T\\)-choice number \\(T\\text{-ch}(G)\\) of a graph \\(G\\) is the smallest number \\(k\\) such that \\(G\\) has an \\(S\\)-list \\(T\\)-coloring for every collection of sets \\(S(v)\\) of size \\(k\\) each. Exact values and bounds on the \\(T_{r,s}\\)-choice numbers where \\(T_{r,s}=\\{0,s,2s,\\ldots ,rs\\}\\) are presented for even cycles, notably that \\(T_{r,s} \\text{-ch}(C_{2n})=2r+2\\) if \\(n\\geq r+1\\). Other bounds are obtained by applying algebraic and probabilistic techniques, such as that \\(T\\text{-ch}(C_{2n})\\leq 2|T|\\) if \\(0\\in T\\), and \\(c_{1}r \\log n\\leq T_{r,s} \\text{-ch}(K_{n,n})\\leq c_{2}r \\log n\\) for some absolute positive constants \\(c_{1}\\), \\(c_{2}\\).   Notice that the \\(T_{r,s}\\)-choice numbers for even cycles were obtained independently by \\textit{Barry A. Tesman} in his thesis [\\(T\\)-colorings, list \\(T\\)-colorings, and set \\(T\\)-colorings of graphs, Ph.D. thesis, Dept. Math., Rutgers University, New Brunswick, NJ (1989)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1383364$D883ACAC-6261-4A14-9A9C-F17ADEE180DC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1383364$730B88DF-6E83-4F61-AEE9-910781913359","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b379324673e19027e24be1ad623ceba48deafe9","datavalue":{"value":"1139428","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1383364$049AAFF4-360C-4B6B-81FA-1E47F712DF2B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cde432f921930d5b95bba296d4907cc20c2a7757","datavalue":{"value":"\\(T\\)-choosability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1383364$D8E7E9DB-67B2-4045-8E14-A6C60E25B7E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"940f1227b30693b703fbec3376022735e78ac900","datavalue":{"value":"\\(S\\)-list \\(T\\)-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1383364$C82D59C4-2710-4AE0-8516-DD8F7BE8F610","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85dfdbd7a975d6137b355769addaba184ea21dc4","datavalue":{"value":"vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1383364$568C0A0B-123A-44A5-A9F7-F1AE0971194E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9638f60d085423aa90e9a173fd4e171ea698f00f","datavalue":{"value":"\\(T\\)-choice number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1383364$D7D4960D-168F-4222-8815-5D55901C6023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5dfb286f2434944d3b5dec33dcd6ce0cd061010","datavalue":{"value":"even cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1383364$8678DA2B-AF54-470E-8F97-2D76ED38C8BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b87d7fc48c526f3af094f6b96557684b388465a5","datavalue":{"value":"complete bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1383364$9BC0F364-4F43-44AB-BB87-257DD1BBD192","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1383364$303E0F76-5760-4B68-AA65-4D47EAAB3205","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":"Q1383364$57BBFDF0-7036-4389-AE58-7ED46F4166BD","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":"Q1383364$B9E0564B-9279-4E0D-A4F8-7C41D0A056DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdd0676f008d3d35603ace258b7c421e863d9a84","datavalue":{"value":{"entity-type":"item","numeric-id":1196681,"id":"Q1196681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1383364$6A5C17A9-6A12-4B49-9CE8-9151918CBE9D","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":"Q1383364$E90D0BCB-3C01-4651-98BA-B5F5DC4B30A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bc7b0f82e42c56ee306811b6c3df8af19432e03","datavalue":{"value":{"entity-type":"item","numeric-id":1231783,"id":"Q1231783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1383364$0DB03C4E-87C4-4803-802C-6131C3B4E30A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3bf56b7e27f34b97f940a7182b5319066422dd1","datavalue":{"value":{"entity-type":"item","numeric-id":3993187,"id":"Q3993187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1383364$E8679F8A-38C7-4EED-A019-00974EC2D82B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e6e0627601eb678357cd6a182e4c3a611cabaca","datavalue":{"value":{"entity-type":"item","numeric-id":1182897,"id":"Q1182897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1383364$7D5FD73B-FBAE-4F51-8A57-5F1FC6E0562B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b048e550daccef3ab3d36df1ef2635b07519043","datavalue":{"value":{"entity-type":"item","numeric-id":1309815,"id":"Q1309815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1383364$472D054D-62AD-4F30-9E68-E86869AEBE2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6856371bcaf691a60c649e21fac9e49211a0b72f","datavalue":{"value":{"entity-type":"item","numeric-id":3115277,"id":"Q3115277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1383364$C39C7B14-F2A6-4030-A8D1-DB2766EAD313","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"18714ac32d6e7891922a72544059376be82dc194","datavalue":{"value":"W2114919740","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1383364$0F3DB7E8-C86F-4CE5-A1AE-E605FE6DB2C8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8ab7a0f0a695ab22531e5b3bca3969ef856fd87","datavalue":{"value":{"entity-type":"item","numeric-id":1377778,"id":"Q1377778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8654cc5c1975e912cdf3ce2109800c3498c5952","datavalue":{"value":{"amount":"+0.9309009909629822","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":"Q1383364$4BB2197B-A1E5-492E-95AC-40BC16A7AEFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"628cd6df3cb60600446176ffb63fce80f1a798c5","datavalue":{"value":{"entity-type":"item","numeric-id":2643324,"id":"Q2643324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a078ecfbf33b498f03d92f3142b01e925c4e6391","datavalue":{"value":{"amount":"+0.8613935708999634","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":"Q1383364$66DA178B-7CB6-4E29-95B0-7372EA70252D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be34a8eafbc11535334910f3baa46cfd85129294","datavalue":{"value":{"entity-type":"item","numeric-id":3110121,"id":"Q3110121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e1537491dbbdb9be15370bd182a1b57dca5c680","datavalue":{"value":{"amount":"+0.8554715514183044","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":"Q1383364$5F17FCB7-833B-4506-88E1-C55261A189C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01f6859100d34590e8e689609e91dc7fe90a56f8","datavalue":{"value":{"entity-type":"item","numeric-id":2462372,"id":"Q2462372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c1836ba70c62d349dc50eca2e69e14ac1659cd0","datavalue":{"value":{"amount":"+0.8361161947250366","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":"Q1383364$755838A7-C7B3-4694-A21B-898B8732EEDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c16227b31f84f4ce14990e14449330d3f7e80a21","datavalue":{"value":{"entity-type":"item","numeric-id":4893602,"id":"Q4893602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb7816e2c9d1d3951153e5384ec59133cdb20a1a","datavalue":{"value":{"amount":"+0.8353537917137146","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":"Q1383364$82A0B336-EED1-4383-88DC-C48A4F1DE3FB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"\\(T\\)-choosability in graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/%5C(T%5C)-choosability_in_graphs"}}}}}