{"entities":{"Q2380218":{"pageid":2390961,"ns":120,"title":"Item:Q2380218","lastrevid":50939036,"modified":"2026-01-15T20:26:03Z","type":"item","id":"Q2380218","labels":{"en":{"language":"en","value":"A note on \\(K^-_{\\Delta +1}\\)-free precolouring with \\(\\Delta\\) colours"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5686767"}},"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":"Q2380218$5F26E61C-58B4-481E-B4D1-0EDD01650560","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"777f6f1351153e21f7e313a68a172ae9a870e597","datavalue":{"value":{"text":"A note on \\(K^-_{\\Delta +1}\\)-free precolouring with \\(\\Delta\\) colours","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2380218$A5711FF9-9EE3-44E1-9974-3CD695708D2D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"df4007970bd1b842c4873a5d60eb0e89ab47e3c6","datavalue":{"value":"1186.05058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380218$803C5311-AF0E-4154-8E17-E647617FFDF5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9faceccf6c94069385e9bb75a38ba1d338a338d7","datavalue":{"value":{"entity-type":"item","numeric-id":407522,"id":"Q407522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380218$B5BEF4AA-9102-4945-820A-9913F806B78C","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":"Q2380218$2635A868-97C2-4F89-91ED-1CC0B368DEFF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"143e8774a45e663375c24b3b343519cf2933b18c","datavalue":{"value":{"time":"+2010-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2380218$EB124963-6A6C-4B9C-98DD-77DE6FC7D659","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d750c5f6c49081d0c468431a7ce71ee51eec49df","datavalue":{"value":"https://eudml.org/doc/224093","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380218$ED6A90F2-CB2A-4AB0-8BC3-D38AC5694B46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"271dd0f04c29387fc05de428b28921110e882fef","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1n28.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380218$BEFA98AA-EF16-4236-8365-FC749985C959","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1c539419e99abfffd67d4ec5a74da0491cfe9fe7","datavalue":{"value":"Summary: Let \\(G\\) be a simple graph of maximum degree \\(\\Delta\\geq 3\\), not containing \\(K_{\\Delta+1}\\), and \\({\\mathcal L}\\) a list assignment to \\(V(G)\\) such that \\(|{\\mathcal L}(v)|= \\Delta\\) for all \\(v\\in V(G)\\). Given a set \\(P\\subset V(G)\\) of pairwise distance at least \\(d\\) then \\textit{M. O. Albertson, A. V. Kostochka} and \\textit{D. B. West} [SIAM J. Discrete Math. 18, No.~3, 542--553 (2005; Zbl 1069.05031)] and \\textit{M. Axenovich} [Electron. J. Comb. 10, Research paper N1, 5 p. (2003); printed version J. Comb. 10, No.~1 (2003; Zbl 1017.05041)] have shown that every \\({\\mathcal L}\\)-precolouring of \\(P\\) extends to a \\({\\mathcal L}\\)-colouring of \\(G\\) provided \\(d\\geq 8\\).  Let \\(K_{\\Delta+1}^-\\) denote the graph \\(K_{\\Delta+1}\\) with one edge removed. In this paper, we consider the problem above and the effect on the pairwise distance required when we additionally forbid either \\(K_{\\Delta+1}^-\\) or \\(K_\\Delta\\) as a subgraph of \\(G\\). We have the corollary that an extra assumption of 3-edge-connectivity in the above result is sufficient to reduce this distance from 8 to 4.  This bound is sharp with respect to both the connectivity and distance. In particular, this corrects the results of \\textit{M. Voigt} [SIAM J. Discrete Math. 21, No.~1, 258--263 (2007; Zbl 1139.05320); Discrete Math. 309, No.~15, 4926--4930 (2009; Zbl 1209.05102)] for which counterexamples are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380218$1084DF50-5F8B-421C-8DEE-A2AF80FD7DEB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380218$DF57759D-53CF-42D2-9457-1005B29F4755","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380218$82D2CFD0-FCFE-4A89-B2CC-D5005C5A2508","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380218$1C70815D-3C98-4D91-96CA-AA7F84C0F9CD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3c94bcdc83910ade7791dde2a676e30816b47d1b","datavalue":{"value":"5686767","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380218$2E287FFA-B1A9-4B23-BAF7-E7304093F12C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66bee96a5226c0739d1922a032582e1602012680","datavalue":{"value":"precolouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380218$C86CC751-3290-4337-AAC1-4504C5382694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cad7d3c28c57bb20ad55561264ac04062cb0d524","datavalue":{"value":"pairwise distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380218$28EAB3B7-BA93-4086-91F2-2A051B2B2F31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380218$314B16DB-778F-4707-8D72-263CAB8D0039","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":"Q2380218$D3B4FBCB-DBEE-4D54-9E3D-E6D8313DA09E","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"168f9793f6a1354132f5b2bd74d6a39aebec3863","datavalue":{"value":"bafkreiat6lp5diqjvsubiqbsiktumyrz3usjrcst7xpsqhuuuuw2nnuqfi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380218$638DDA03-F8AA-4100-8848-2E2CDBA29FF5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0c4042e1dd950afb4b99c20f86678829b3de649","datavalue":{"value":{"entity-type":"item","numeric-id":5454276,"id":"Q5454276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f054cb443bea825a69fbc34b9ae96c495ace77e","datavalue":{"value":{"amount":"+0.8603896498680115","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":"Q2380218$19CB0BB6-9797-4656-A25E-BA503495D792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ae52da5e1236a2d9363c2f182dcb76eee3e41bb","datavalue":{"value":{"entity-type":"item","numeric-id":1044924,"id":"Q1044924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"320210d15b26686323a4bfc90e2903bf9451db6d","datavalue":{"value":{"amount":"+0.8479951620101929","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":"Q2380218$0793F391-67B3-4745-892D-79F54A84020E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1802e9aa6dd79e64d7e5f58a7dfed0f6ad41ac8f","datavalue":{"value":{"entity-type":"item","numeric-id":5317568,"id":"Q5317568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"186d89f5c5518753b6df8a54fee7ea3304c6ca12","datavalue":{"value":{"amount":"+0.8382297158241272","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":"Q2380218$F0ADD601-1AEC-4C78-97F1-FBF4DA9A32DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0147147aa96cca115652b482e73164fee10868f4","datavalue":{"value":{"entity-type":"item","numeric-id":5207466,"id":"Q5207466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04bf352239a4d9c64267f9cff5e98fea20c6a620","datavalue":{"value":{"amount":"+0.8316635489463806","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":"Q2380218$7D028C49-555C-46CC-9740-713838C86E99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"138d36de192130b7c13d6d09dca2fa6aa706a2b2","datavalue":{"value":{"entity-type":"item","numeric-id":3633010,"id":"Q3633010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ca003176b8f7f44fb072455d40d242295bf4576","datavalue":{"value":{"amount":"+0.8096059560775757","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":"Q2380218$143CDE12-363A-4111-B720-FFB3B488AABD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2380218","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2380218"}}}}}