{"entities":{"Q941324":{"pageid":943172,"ns":120,"title":"Item:Q941324","lastrevid":65537709,"modified":"2026-04-12T03:17:16Z","type":"item","id":"Q941324","labels":{"en":{"language":"en","value":"List-colouring the square of a \\(K_4\\)-minor-free graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5321275"}},"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":"Q941324$69080DE1-5368-495B-9419-5488143FDED4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"508e414d62e0fdff84664059b9d0b639cc1f13f9","datavalue":{"value":{"text":"List-colouring the square of a \\(K_4\\)-minor-free graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q941324$CA888ED1-1561-40C1-87CB-E1C5E6EA70EA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"50deafc29fce71f02db1cc1e1073bcb377d9c781","datavalue":{"value":"1155.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941324$14F467D8-12FA-414D-A976-EDFAA83FF620","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd371fce3eaa70c07f273ce7ca5e29ac326c190b","datavalue":{"value":{"entity-type":"item","numeric-id":714511,"id":"Q714511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941324$7AC705D1-F264-46C3-82D9-283D3A0D362B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f7f1fcbb6559f616fb43cbccc2a4fe05892fcdc","datavalue":{"value":{"entity-type":"item","numeric-id":214988,"id":"Q214988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941324$869ADDC5-7DAC-4E42-8446-408215F6D018","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941324$976F45E0-D471-4A7E-9547-CA3B07196AD1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2bf0f0ee9c49018dff9c641c5da1a78a5da873e5","datavalue":{"value":{"time":"+2008-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q941324$2A43345C-D84E-4709-957C-1A4128E459A2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"407d412c67a44aeb08d8415fe5ef86b7706cd0ec","datavalue":{"value":"The square \\(G^2\\) of a graph \\(G\\) has the same vertex set as \\(G\\), and two vertices are adjacent in \\(G^2\\) if they are within distance two of each other in \\(G\\). The list chromatic number of \\(G\\) is denoted by \\(\\text{ch}(G)\\). The degeneracy of \\(G\\) is the smallest integer \\(k\\) such that every subgraph of \\(G\\) contains a vertex with degree at most \\(k\\) and denoted degeneracy\\((G)\\). The following is proved in this paper. Let \\(G\\) be a \\(K_4\\)-minor-free graph with maximum degree \\(\\Delta\\). Then  \\[ \\text{ch}(G^2) \\leq \\begin{cases} \\Delta + 3 &\\text{if }\\Delta=2\\text{ or }3; \\\\ \\left\\lfloor \\frac{3}{2} \\Delta \\right\\rfloor + 1&\\text{if }\\Delta \\geq 4,\\end{cases} \\]  and we also have  \\[ \\text{degeneracy}(G^2) \\leq \\begin{cases} \\Delta + 2 &\\text{if }\\Delta= 2\\text{ or }3; \\\\ \\left\\lceil \\frac{3}{2} \\Delta \\right\\rceil &\\text{if }\\Delta \\geq 4.\\end{cases} \\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q941324$D06D16AC-550A-496E-8698-8734D28E9B66","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941324$42D3B103-727D-4A19-BA0D-1FDBC2D76091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941324$403E6889-9A66-4A73-BCCD-1489DD807357","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e8199a600726d8f62558c9e0ef37411b9c6eb130","datavalue":{"value":"5321275","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941324$A825ADB6-44C5-46F8-8921-B8237FFF07C9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f51628859d3741a7d4b3d92b1098364d202d37a4","datavalue":{"value":"choosability","type":"string"},"datatype":"string"},"type":"statement","id":"Q941324$6C1833A1-36CA-43D7-A508-FD9762858D74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0886d2a1a6c8e13c6770125edf63deb8a5245d27","datavalue":{"value":"minor-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q941324$8D749115-9DC9-4715-84BC-EF0C815CA6E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a69c16b8abd056d77bece921069261969ff1ddb","datavalue":{"value":"list square colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q941324$3E1780F3-EB51-4503-9FFD-B4CB4B0C2C1B","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":"Q941324$4846206F-19C1-457E-979B-1EE4C13F73A3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e2bb5fed8f0f33c532e9dcf0ee1bd4947ace773f","datavalue":{"value":"https://doi.org/10.1016/j.disc.2007.07.102","type":"string"},"datatype":"url"},"type":"statement","id":"Q941324$90689B05-B63E-4B86-B137-C6B864FB1CAB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6e9ed49860bbf52b46b1df1ccac08d0ba1209703","datavalue":{"value":"W1555403707","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941324$FA4B88F2-493E-4D99-9174-9C96F798A155","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"85cfa63f67ed3743ed6d983c37c02f4185c5f671","datavalue":{"value":{"entity-type":"item","numeric-id":5811782,"id":"Q5811782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941324$CA8EE799-21D9-4B12-84B4-B256C13A482F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d47ff954cab26fbcf3506ef450f27d865d70b594","datavalue":{"value":{"entity-type":"item","numeric-id":5948972,"id":"Q5948972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941324$7BC7D261-A4AA-447D-ABA0-2C12A97F3078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db48ff42d5acde172a2e6824b921f40ac66c2b62","datavalue":{"value":{"entity-type":"item","numeric-id":1402088,"id":"Q1402088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941324$CD201454-A461-4DBE-82A0-564BA93F35E1","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":"Q941324$8E21E20C-32EB-4FF3-847D-D217391D426E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48e74df630efeb15a94e9bed909804646715b3eb","datavalue":{"value":{"entity-type":"item","numeric-id":2741180,"id":"Q2741180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941324$05DB3734-6AFA-409E-9BA4-A97AFEBAABDF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1a90af20a086354377c1f5502be5aa6d6b44231d","datavalue":{"value":"10.1016/J.DISC.2007.07.102","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941324$F6A20059-404B-4F18-BAE5-15BDD53CDB0E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6400368c77f18713a7c43f51ef39470e0e108ecd","datavalue":{"value":{"entity-type":"item","numeric-id":1402088,"id":"Q1402088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc1a6380e751c1d46034e97111bce37c74e4febb","datavalue":{"value":{"amount":"+0.8904349207878113","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":"Q941324$C145F2A7-A1C6-4DE7-A82A-D5AE3D2C9848","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3253fbd32037e2e8303450108249514e45b67be","datavalue":{"value":{"entity-type":"item","numeric-id":2918556,"id":"Q2918556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20bd0b0c74d2290eed2584799f1f58ab827cb627","datavalue":{"value":{"amount":"+0.8874149322509766","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":"Q941324$65C3FDDC-E215-4B7E-B654-840E472D1393","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ece70a8e5bad02c09e6887f6f7b0a12f2b11e653","datavalue":{"value":{"entity-type":"item","numeric-id":1045198,"id":"Q1045198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c56e0132240b0ae932f1e49369f3e699fdb5e468","datavalue":{"value":{"amount":"+0.8519569039344788","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":"Q941324$9810C27D-D884-44A7-A2DC-848582F1B55D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0395eb76cc383577141cc490cbf8c58d9ea90092","datavalue":{"value":{"entity-type":"item","numeric-id":2658379,"id":"Q2658379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d52a285f413dd736ba025303fd6230a527b10a51","datavalue":{"value":{"amount":"+0.8072701692581177","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":"Q941324$554B71A5-DD6F-4283-934B-883BCF03EDDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb688dba3187486c812c9d9d0c2451514130caf4","datavalue":{"value":{"entity-type":"item","numeric-id":2876030,"id":"Q2876030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3059043fddef71a6ef908e716109c2f721772772","datavalue":{"value":{"amount":"+0.8015880584716797","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":"Q941324$017E383C-B3BD-47CC-8EEA-7DBED28259ED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"List-colouring the square of a \\(K 4\\)-minor-free graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/List-colouring_the_square_of_a_%5C(K_4%5C)-minor-free_graph"}}}}}