{"entities":{"Q2496207":{"pageid":2506950,"ns":120,"title":"Item:Q2496207","lastrevid":55905019,"modified":"2026-02-21T00:45:00Z","type":"item","id":"Q2496207","labels":{"en":{"language":"en","value":"A relation between choosability and uniquely list colorability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5040284"}},"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":"Q2496207$E5F29D8E-B47F-4D3F-ABC2-5DE3012C91A5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fbe71c7dd6c9dd414d9406d8d10cfe40062ad1fe","datavalue":{"value":{"text":"A relation between choosability and uniquely list colorability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2496207$A5E67AA8-CAFA-4584-937D-E9461763ABD5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"97dee83ce8a04ae3ba7d02fd3d36baef4cd30cb3","datavalue":{"value":"1100.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2496207$071724F7-F215-4833-906D-93A7C2864F1F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c74ad410e3b014e4b9235c25bf39c330ea4e07da","datavalue":{"value":{"entity-type":"item","numeric-id":1613345,"id":"Q1613345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$596C47B7-DACF-4803-8CE5-CF1BCFFCBAC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"be42c7caeb6318736e231047adcf0f213dc3e6da","datavalue":{"value":{"entity-type":"item","numeric-id":277492,"id":"Q277492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$2B6EFD5A-9A51-43DE-BE8C-970F00178E12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0a10103d2ba783e47a71bc1d8056c5b62a2098c","datavalue":{"value":{"entity-type":"item","numeric-id":547288,"id":"Q547288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$C03E89F2-2730-4994-A905-AFC14E6046F6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$7E7DD6F8-9576-4AA0-975F-7208A2E80175","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"695354130dab3a786d23413cb8a043a7f99b90ed","datavalue":{"value":{"time":"+2006-07-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":"Q2496207$E53590A5-A8BB-47CE-8B4F-9FEC782A6380","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b2c089f801701e2d1ef13d3fece3c3ebdf361bff","datavalue":{"value":"A list assignment \\(L\\) of a graph \\(G\\) is a function that assigns a set of colors to each vertex of \\(G\\). Graph \\(G\\) is (uniquely) \\(L\\)-colorable if there is at least (exactly) one function that assigns to each vertex \\(v\\) of \\(G\\) a color from \\(L(v)\\) such that any two adjacent vertices are assigned distinct colors. The definitions of an edge-list assignment and a uniquely \\(L\\)-edge-colorable graph are analogous.  The main result of this paper says that if \\(G\\) is a uniquely \\(L\\)-colorable graph with \\(n\\) vertices and \\(m\\) edges such that the sum of \\(| L(v)| \\) over all vertices \\(v\\) of \\(G\\) equals \\(n+m\\), then \\(G\\) is also \\(L'\\)-colorable for any list assignment \\(L'\\) satisfying \\(| L'(v)| =| L(v)| \\) for each vertex \\(v\\) of \\(G\\).  The proof is based on an algebraic technique developed by \\textit{N. Alon} and \\textit{M. Tarsi} [Combinatorica 12, No.~2, 125--134 (1992; Zbl 0756.05049)]. As a corollary, it is shown that if a connected non-regular multigraph with an edge-list assignment \\(L\\) satisfies \\(L(\\{u,v\\})=\\max\\{d(u),d(v)\\}\\) for each edge \\(\\{u,v\\}\\), then it is not uniquely \\(L\\)-edge-colorable. The authors conjecture that this result holds also for any regular graph \\(G\\) of degree at least two and verify it in the case that \\(G\\) is bipartite.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2496207$322065EE-432B-4DF0-8ECB-F05468777C29","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c0617d45f23e5dfc7fb0eb4ddcab2f46301293e8","datavalue":{"value":{"entity-type":"item","numeric-id":414470,"id":"Q414470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$6E8246FD-329D-493B-B921-F606E3D3FDE8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2496207$61246E01-CA3F-423A-BB38-2B7A8E412989","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bc0640b413b984297c3999a7465cd16d9f77a6fd","datavalue":{"value":"5040284","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2496207$4B6AD057-A5F4-48E2-AC47-2B811FECBB6E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"948b8134d7c1010c7dc9b8997f8744a9b8f91a82","datavalue":{"value":"unique list coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2496207$6E0F55CA-6C04-499A-8DA3-48520CC167F5","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":"Q2496207$62D2CAD3-FAC4-4F13-AAEC-6793E08E3F28","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c2d43cbd52e1b76c4d90892279ac3a6b05c86786","datavalue":{"value":"https://doi.org/10.1016/j.jctb.2005.12.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q2496207$56CD1F47-961B-48FA-A20F-49AAF8EDA440","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"655a514e6f51e929e406e6bb2620ab312a5c5284","datavalue":{"value":"W2049904819","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2496207$88395809-47DA-464D-988B-6E1C9CD0E1AA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed82b0773b41da9b400b06b436800f50e9936ee2","datavalue":{"value":{"entity-type":"item","numeric-id":1850550,"id":"Q1850550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$719BC8BF-0B4F-4A3C-98EC-4097C6045F19","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":"Q2496207$D5020855-0728-43B6-9D42-9B06C9612456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"006f0f2f91646a7270feb56283055eaf50cccc1b","datavalue":{"value":{"entity-type":"item","numeric-id":4111592,"id":"Q4111592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$0BB92774-15E5-43E7-9EDF-8EAAD5B204CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb8b23be685b19bdd0313eaaa79ce5140147fe55","datavalue":{"value":{"entity-type":"item","numeric-id":1366604,"id":"Q1366604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$10DC4EBF-F02D-4CB5-9D78-378C498A8FD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7ce97036ffd0a1347b57fc59e633d019cd05d2c","datavalue":{"value":{"entity-type":"item","numeric-id":1210549,"id":"Q1210549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$555D059A-803D-4D64-BC2B-5AE82688482C","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":"Q2496207$186F13F5-6110-4A90-BC53-0FE2EA5F1CC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49b1ea8c71c16680a80daa5a278988ba0f26dce6","datavalue":{"value":{"entity-type":"item","numeric-id":1892837,"id":"Q1892837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$1B0F0875-01A3-4687-968A-ACADD51EE2EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3022aa8446432fb3ba1ed42c9c8b9f90d4d5bc23","datavalue":{"value":{"entity-type":"item","numeric-id":1613346,"id":"Q1613346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$A148B380-61E9-465A-9E17-74D446B53916","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa59e5a35275b91ef5a7e44de99f5525aca3fc43","datavalue":{"value":{"entity-type":"item","numeric-id":4020707,"id":"Q4020707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$FBA0ED50-B3D8-42A4-9F2B-B48205C40A2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9e78146ebf190dc43ced436134c36775d6d42e2","datavalue":{"value":{"entity-type":"item","numeric-id":5565634,"id":"Q5565634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$A2DE9E8C-F3AE-4835-BE1C-FF2E28150E23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35184f581a4fa42ee779b59d5e27eea0c204219f","datavalue":{"value":{"entity-type":"item","numeric-id":5931450,"id":"Q5931450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$28B8E6AB-712A-47CA-99D4-D535FBF1D70B","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":"Q2496207$76CF0FDD-0574-444A-878A-06490DA2895E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89c61921feb106a77eacba4de5f3a1c12d362b1","datavalue":{"value":{"entity-type":"item","numeric-id":2641312,"id":"Q2641312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496207$AE96678B-B558-4E5F-9BC1-5E9CD109C72F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"476d052a7a8265a686d4d63bcd474d3fd0f4ff12","datavalue":{"value":"10.1016/J.JCTB.2005.12.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2496207$4D581C3F-D65F-48A4-B925-5A7AAD093833","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70ec8d25dfebe651b14f39f3ab9a538db7615152","datavalue":{"value":{"entity-type":"item","numeric-id":1366604,"id":"Q1366604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1380cf01a8171b87b06017ed30968ed17694013","datavalue":{"value":{"amount":"+0.7784068","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":"Q2496207$B60D417A-E599-4305-8D40-53ED98A8162A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4e28aeb2651848aedb4dab965943fec11d2bd27","datavalue":{"value":{"entity-type":"item","numeric-id":4898487,"id":"Q4898487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"573c377803f4e5a16bb23cb8b577a79c0cfa50d8","datavalue":{"value":{"amount":"+0.7742288","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":"Q2496207$0A73E81E-BB0E-4CA4-87C6-F0F1A9878C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fdbdf7920e585e0ae99661a7b342f46426fe450","datavalue":{"value":{"entity-type":"item","numeric-id":4386303,"id":"Q4386303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86920c3c627ab72660fed96ecaf5d382d28c0e25","datavalue":{"value":{"amount":"+0.7613348","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":"Q2496207$28DC0F34-2D8C-4ED7-B1F3-0FA8FC281A5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d121445276eecab2b4f2e7380e8dd68a3830aebb","datavalue":{"value":{"entity-type":"item","numeric-id":2761069,"id":"Q2761069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1aafe9441fee269acce581606675c368c5154d67","datavalue":{"value":{"amount":"+0.75331664","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":"Q2496207$44E42DF0-67F5-4B8D-BD43-28742596D7A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89a06b9adda3034853396659dec818714cf3fb34","datavalue":{"value":{"entity-type":"item","numeric-id":5207462,"id":"Q5207462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cb86b33e539ce24ee25f298b4d8eb4fa56f3fcc","datavalue":{"value":{"amount":"+0.7499784","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":"Q2496207$5A377BDC-13D3-4ED4-A5CA-F2F9BBA73E1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"388b34d9cc5b0042dc02e6f1ee3141e91281c427","datavalue":{"value":{"entity-type":"item","numeric-id":817777,"id":"Q817777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a25249222c06f28c1c8005e43c1105e55e8d7f00","datavalue":{"value":{"amount":"+0.74476236","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":"Q2496207$9C8E2FCA-8E7A-44FB-888F-018B7C9BDC1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"224373ee3ad0c5b393b59972e98172f048fcebe3","datavalue":{"value":{"entity-type":"item","numeric-id":4329136,"id":"Q4329136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20d752f7a775a386abe8dbd746846abd15bfd801","datavalue":{"value":{"amount":"+0.7408303","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":"Q2496207$5A0E9443-118A-4AD2-A3C7-66371420CF7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f54ba6046013211f437393869c78329dd69253eb","datavalue":{"value":{"entity-type":"item","numeric-id":1301722,"id":"Q1301722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbea7ad17bca17ba6a2c2c140dcf55b9d9b34a3c","datavalue":{"value":{"amount":"+0.73861533","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":"Q2496207$62E54EB6-5C82-4B8E-9122-4DD976808463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3976874b0b72e2f85834b46ca9ceb45ff7ae565","datavalue":{"value":{"entity-type":"item","numeric-id":1613346,"id":"Q1613346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80bc99a66878941f9a578d827d60219cf550ef12","datavalue":{"value":{"amount":"+0.738516","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":"Q2496207$0249F257-AD78-4EE8-8197-AE716A81ED2D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2496207","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2496207"}}}}}