{"entities":{"Q668046":{"pageid":669895,"ns":120,"title":"Item:Q668046","lastrevid":63519822,"modified":"2026-04-11T13:43:17Z","type":"item","id":"Q668046","labels":{"en":{"language":"en","value":"On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7032075"}},"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":"Q668046$C4BC682A-1B55-4362-9BC4-821D8A104853","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ca1341be7c86e900442477492a71805dd952236a","datavalue":{"value":{"text":"On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q668046$8AAF8C34-3A37-44F7-AD04-BBACFB450BBB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a6b58bf6b73c42e761016e913710ef69fcb2daaf","datavalue":{"value":"1409.05110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668046$E5BEDAAD-44C1-481C-8543-5CF8476ABE30","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d7970fbd616a2ef90b680852899a50b28bb12f1c","datavalue":{"value":{"entity-type":"item","numeric-id":668045,"id":"Q668045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$E3D92A9A-E6C0-4CA1-BFED-9FB3C111C392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8dada8c15e16d9b57e5b40b6a28a3a309c3fcd25","datavalue":{"value":{"entity-type":"item","numeric-id":1756125,"id":"Q1756125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$B5D1DCDB-4ED1-47B2-A18A-1C48070DAEA5","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":"Q668046$980B8BBB-4275-48AC-A661-453A1CAAC3DF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c236a5296bce37f0e3594963375752714d7f6e86","datavalue":{"value":{"time":"+2019-03-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q668046$9E3BA440-AD5C-45DF-B3FF-1AC33AF04545","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1523c13f4d9dcd0b8229e93caf8fb48fb99855f1","datavalue":{"value":"https://arxiv.org/abs/1803.07455","type":"string"},"datatype":"url"},"type":"statement","id":"Q668046$5A6F7F9F-066C-4C28-9FE1-64C79170FE20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"40915f08b8f952c235ba30dd87cf257bbc443359","datavalue":{"value":"https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p3","type":"string"},"datatype":"url"},"type":"statement","id":"Q668046$57E98BD7-5758-468B-B02B-474F4A395DC8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b3fddb786e787e7248aabd51ddc7133aa07bf5f4","datavalue":{"value":"Summary: We study the list chromatic number of Cartesian products of graphs through the Alon-Tarsi number as defined by \\textit{T. R. Jensen} and \\textit{B. Toft} in their seminal book on graph coloring problems [Graph coloring problems. New York, NY: John Wiley \\& Sons (1995; Zbl 0855.05054)]. The \\textit{Alon-Tarsi number} of \\(G\\), \\(AT(G)\\), is the smallest \\(k\\) for which there is an orientation, \\(D\\), of \\(G\\) with max indegree \\(k\\!-\\!1\\) such that the number of even and odd circulations contained in \\(D\\) are different. It is known that \\(\\chi(G) \\leq \\chi_\\ell(G) \\leq \\chi_p(G) \\leq AT(G)\\), where \\(\\chi(G)\\) is the chromatic number, \\(\\chi_\\ell(G)\\) is the list chromatic number, and \\(\\chi_p(G)\\) is the paint number of \\(G\\). In this paper we find families of graphs \\(G\\) and \\(H\\) such that \\(\\chi(G \\square H) = AT(G \\square H)\\), reducing this sequence of inequalities to equality.  We show that the Alon-Tarsi number of the Cartesian product of an odd cycle and a path is always equal to 3. This result is then extended to show that if \\(G\\) is an odd cycle or a complete graph and \\(H\\) is a graph on at least two vertices containing the Hamilton path \\(w_1, w_2, \\dots, w_n\\) such that for each \\(i\\), \\(w_i\\) has a most \\(k\\) neighbors among \\(w_1, w_2, \\dots, w_{i-1}\\), then \\(AT(G \\square H) \\leq \\Delta(G)+k\\) where \\(\\Delta(G)\\) is the maximum degree of \\(G\\). We discuss other extensions for \\(G \\square H\\), where \\(G\\) is such that \\(V(G)\\) can be partitioned into odd cycles and complete graphs, and \\(H\\) is a graph containing a Hamiltonian path. We apply these bounds to get chromatic-choosable Cartesian products, in fact we show that these families of graphs have \\(\\chi(G) = AT(G)\\), improving previously known bounds.","type":"string"},"datatype":"string"},"type":"statement","id":"Q668046$D0E6BB75-4F65-4264-851A-9D4609AD4A28","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668046$F965B9EF-2C91-4685-A977-EFECCFBDFA47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668046$8A22986B-B5F9-4B5C-9440-A6EBDC99927D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668046$36EF5FD6-5DFD-442E-95E3-B8F74522E9F8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bd96b618f962e0671f88ecb9ba248dd11b34e040","datavalue":{"value":"7032075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668046$BEE247CD-0AA0-417C-9DB8-ADCA7039C22E","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":"Q668046$5486D012-5249-488F-8EBC-97982D40C959","rank":"normal"}],"P223":[{"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":"Q668046$3DC7BE81-DF27-4591-992C-F3363E430F52","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":"Q668046$FF2ACFF1-40CC-4403-880C-9F10F69EB6D2","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":"Q668046$6CCEB367-A156-471E-B0FD-2D6159DE78FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00e811b31cd3266294ef913e447c3895e137a57f","datavalue":{"value":{"entity-type":"item","numeric-id":2501567,"id":"Q2501567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$49DCCE6C-B1A3-47DC-BA93-C172528D3B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9694daec953882df27dc04164c3aa68ada151b4","datavalue":{"value":{"entity-type":"item","numeric-id":2448254,"id":"Q2448254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$B0F2A0F0-C535-431A-9026-DA967A114694","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":"Q668046$4F28BCA1-5EF3-41F9-92F8-082F5EA3EDE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c0c0b4fbb03688de9dbe8c20f9adff708be1653","datavalue":{"value":{"entity-type":"item","numeric-id":1356789,"id":"Q1356789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$62872766-FAD2-4B1A-A343-36751FAE143D","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":"Q668046$D076CDC5-C96C-4422-A53A-55532BDC5E76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a23b6c403338a27337d9e49ec3249a1493fd95a8","datavalue":{"value":{"entity-type":"item","numeric-id":651032,"id":"Q651032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$978CB0DB-A823-46ED-9368-6DD1DB63E034","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f855246caf01e7d423da5ddcd02591be6660a7f0","datavalue":{"value":{"entity-type":"item","numeric-id":4857375,"id":"Q4857375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$3DB7AAEE-B942-4B07-90B4-500464B2521C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76f98835e6f985f441b694d31322d18fce00bcfd","datavalue":{"value":{"entity-type":"item","numeric-id":1906118,"id":"Q1906118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$29B527F1-63DA-4DAC-B955-4112020086EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"622b94b2933d32a92d0a166131f7241dff4cfbfd","datavalue":{"value":{"entity-type":"item","numeric-id":2041704,"id":"Q2041704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$46B0F5FC-3C7E-49A8-BB8E-5216541534BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbcf13a934932eba899a1b7b1978f842630a803d","datavalue":{"value":{"entity-type":"item","numeric-id":5251204,"id":"Q5251204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$CDDB1C71-7517-4CBE-AC62-158B96560FF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d0e9d46516ec9cdf0427c4a6de1909c2f4ec26f","datavalue":{"value":{"entity-type":"item","numeric-id":4539876,"id":"Q4539876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$2630AA8F-7C22-45B3-A3BD-BAF6018CC9B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aaf569e4df311fd90a91a5185c6470f0d0d5c268","datavalue":{"value":{"entity-type":"item","numeric-id":1396660,"id":"Q1396660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$3D8E1E72-034D-4247-B0CC-804AA025C466","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bcf2b4c2b6c7326a3acf6bf57028e463e8c28e","datavalue":{"value":{"entity-type":"item","numeric-id":2380232,"id":"Q2380232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$BFC32DAE-9B93-49AF-A632-B6B2DEC8552D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b33b572b7cb6c6ac08be0930cd92b0a3a2b601bd","datavalue":{"value":{"entity-type":"item","numeric-id":2380445,"id":"Q2380445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$ABAD0DFA-DF68-4538-AA94-D7E1FAC99E47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"493f50526d224bb566df651badf502c3465a3278","datavalue":{"value":{"entity-type":"item","numeric-id":4882474,"id":"Q4882474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$AFF5FE00-816A-4523-BD1D-CAE213E3E3C0","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":"Q668046$423C5762-F966-43F9-B328-2A9516A3DBA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"419f6e07f619561ee7d440e7770a99141bd9385d","datavalue":{"value":{"entity-type":"item","numeric-id":1633764,"id":"Q1633764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668046$BFDA61A0-847F-4DFE-B7CD-6E96698EF828","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"700baaea66fe6dd2c47ad640e46a51086ff7a2e2","datavalue":{"value":"bafkreif5gh3oowlvxislizuht6w7x7knrrpmudau5wlho3e7sknwiq5jlq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668046$39C683C0-AD0B-4AC0-9260-BB653C26F8DC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d5f7808844cb205224115554c7b5b175aefcda0","datavalue":{"value":{"entity-type":"item","numeric-id":651032,"id":"Q651032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a2bd821660f728e9d703f7c4754abbe659eefb9","datavalue":{"value":{"amount":"+0.8264406323432922","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":"Q668046$33850FC9-F3FB-49F3-9D9B-5DABACC734FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1af59f2a8fa650face656d0a4e94dfaf1cd4b72","datavalue":{"value":{"entity-type":"item","numeric-id":2077275,"id":"Q2077275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a2122654c062050a28227d4f92673179c9725dd","datavalue":{"value":{"amount":"+0.8168483376502991","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":"Q668046$59EFCED0-E148-4DCB-AD32-EEA5ABEC03F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e64c9f4fd3cb8ead6ea0af910c22e9474cd7dc06","datavalue":{"value":{"entity-type":"item","numeric-id":6171495,"id":"Q6171495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e1c655e3e8741279d81e88f220faf6abfca87db","datavalue":{"value":{"amount":"+0.8153298497200012","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":"Q668046$71F75EF2-621D-4B71-8D90-1E8439F759E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c926bca7c9c29fcf2f1301f8982c1731ad0ec87","datavalue":{"value":{"entity-type":"item","numeric-id":1633764,"id":"Q1633764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a48a6fd2fb2467a494df37e4dc12cfecde09392","datavalue":{"value":{"amount":"+0.8146010637283325","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":"Q668046$A1740D22-AF23-4801-A382-CE1324ED9DF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3851cfabf2d53e9a7641567c2efd81e628b7ac00","datavalue":{"value":{"entity-type":"item","numeric-id":6164660,"id":"Q6164660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e31e8f9dfbee5a81e11fa66060cf78b9fc97309a","datavalue":{"value":{"amount":"+0.8103309869766235","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":"Q668046$3F7D7A98-3E30-459F-A4AB-B04041F0641F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_Alon-Tarsi_number_and_chromatic-choosability_of_Cartesian_products_of_graphs"}}}}}