{"entities":{"Q1567669":{"pageid":1578409,"ns":120,"title":"Item:Q1567669","lastrevid":72213333,"modified":"2026-04-14T03:22:47Z","type":"item","id":"Q1567669","labels":{"en":{"language":"en","value":"Extending partial colorings of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1462324"}},"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":"Q1567669$B7E41544-B654-4F50-BB83-9E935B413564","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ad61868dbe4ed243a8d5adab5de40cd112e6eaa3","datavalue":{"value":{"text":"Extending partial colorings of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1567669$534D836D-58C3-404C-96A5-F1FF0D8E6355","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"463b57cb23133c97e9999db2c86e6d502ae556cb","datavalue":{"value":"0944.05034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567669$F7B46D73-EFC6-4CD9-A2CA-54CE7DE3123E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5158d2a75220d70a26b1f8e626d9df1c5fcc8368","datavalue":{"value":"10.1016/S0012-365X(99)00372-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567669$3169BFDA-04E4-43E1-AD1E-5DC8CDF10604","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":"Q1567669$7C812DDF-9DD9-4442-B249-F5C1C407B3AB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8419f06ab8e0f2e62a9db4d1f2de9ef32bd29c48","datavalue":{"value":{"time":"+2000-09-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1567669$2E70FB6E-6EF5-41B7-98FF-46E9D9FF77D4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"259eeb5de69e75e2b6e5712a0b4104eb452db5b1","datavalue":{"value":"For a graph \\(G\\) let \\(N[W]=\\{v\\in V(G)\\mid v\\) is adjacent to some vertex in \\(W\\}\\cup W\\), \\(N^{0}[W]=W\\) and \\(N^{s+1}[W]=N[N^{s}[W]]\\). Let \\(\\text{Pre}(r,d,t)\\), resp. \\(\\text{PPre}(r,d,t)\\) be the least \\(k\\) such that if \\(G\\) is an \\(r\\)-colorable graph, resp. perfect graph, \\(W=W_{1}\\cup W_{2}\\cup \\ldots \\cup W_{n}\\subset V(G)\\) where \\(\\text{dist}(W_{i},W_{j})\\geq d\\) whenever \\(i\\neq j\\), and \\(f\\) is a \\(k\\)-coloring of \\(W\\) such that \\(f|W_{i}\\) can be extended to an \\(r\\)-coloring of \\(N^{t}[W_{i}]\\) for all \\(i\\), then \\(f\\) can be extended to a \\(k\\)-coloring of \\(G\\). The purpose of this paper is to show how old techniques for coloring highly recursive graphs can be used to prove theorems concerning the extension of a partial coloring of a graph to a total coloring.    It is proved that \\(\\text{Pre}(r,3,0)= r^{2}+r\\), \\(\\text{Pre}(r,d,0)= 2r\\) for all \\(d\\geq 4\\), \\(\\text{Pre}(r,3,1)= r^{2}\\), and \\(\\text{Pre}(r,d,1)\\leq 2r\\) for all \\(d\\geq 4\\). By extracting a proof from \\textit{J. H. Schmerl}'s paper [Can. J. Math. 32, 821-831 (1980; Zbl 0394.05021)] on coloring highly recursive graphs it is shown that \\(\\text{Pre}(r,d,1)= 2r-1\\) for all \\(d\\geq 6\\) and \\(\\text{Pre}(r,d,2)= 2r-1\\) for all \\(d\\geq 5\\). When \\(G\\) is a perfect graph by using a proof from the author's paper [Can. J. Math. 33, 1279-1290 (1981; Zbl 0458.05034)] it is proved that \\(\\text{PPre}(r,4r,2r-1)= r+1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567669$50251A35-324A-40E8-B15E-3007B1BEF0A1","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":"Q1567669$2FFA386D-8265-43D2-9DD2-05CCF2A4ABAC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567669$7D5DD826-1F5C-4AC4-9871-821D74E790C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567669$B3379B65-FFB3-4B22-9FE0-F53ECD340126","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"01afb4d677d53afd354b65f4f3fcb332e6ddfeeb","datavalue":{"value":"1462324","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567669$3858DE37-8319-4D6C-A1F4-3A00A458EDEB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75ac39b75b3e9aaaafdc734ef9ec88cf7ae88a4c","datavalue":{"value":"partial coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567669$E8B75238-F6C8-4C1D-BCCA-90BEFBEB2B49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a38f9a1a7ed93d513352c1fbc76de66d9278135","datavalue":{"value":"highly recursive graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567669$B849FE20-C772-4892-A0C8-EC3BC48DC3FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6072fa2abea179a7709e57b96ad2802601bb845","datavalue":{"value":"perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567669$A47EC8A0-B3EB-43C4-B773-9ECB7DA9C578","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6dbbadbae6ed796cce192545d6f92870af684efe","datavalue":{"value":"\\(k\\)-clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567669$3905206C-524D-434F-B505-A1B540E6C38D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e8e4763e432b6ffd9ef1ff20256862696bdf24ca","datavalue":{"value":{"entity-type":"item","numeric-id":555495,"id":"Q555495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1567669$29A1A9EF-C006-4CD6-9BE1-8ED5652BF043","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":"Q1567669$9E228972-C650-407A-9799-539B61FB26E0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ea4bd49078e1dc374c966599a6a52e7c532563f7","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(99)00372-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1567669$F21D601D-87EF-481C-86CD-EFA16AC2597D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c85a03bda8d4dfdc6da7132adb629e1a647aa9e2","datavalue":{"value":"W2003334245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567669$8A86D830-AF08-4796-9890-FC1D404F7E13","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee1bc4e1e2cce9db911c2da25ffd4a2a926b16aa","datavalue":{"value":{"entity-type":"item","numeric-id":1569052,"id":"Q1569052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"282cc529cd721a12d66df45e09e4c4ea74238391","datavalue":{"value":{"amount":"+0.8695439100265503","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":"Q1567669$6AF65AD1-65FF-4C4E-9D02-471BFC719C7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"845ea0bf368c0e89637e0990ba158ce439fdf582","datavalue":{"value":{"entity-type":"item","numeric-id":4883061,"id":"Q4883061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0989315298769e3c3e127cdf05014ca1cdab9a3d","datavalue":{"value":{"amount":"+0.8475398421287537","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":"Q1567669$D2452A89-82E3-47B1-BF5A-992E8D378381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3574b36ecb43e4d8b50a49137b3fbe4e346c23f4","datavalue":{"value":{"entity-type":"item","numeric-id":5936057,"id":"Q5936057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8432a80aa3826c07dd54e40cb00b130f20f38345","datavalue":{"value":{"amount":"+0.8232977986335754","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":"Q1567669$F6499470-46EA-4CED-99AD-CA1D66AAF143","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Extending partial colorings of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Extending_partial_colorings_of_graphs"}}}}}