{"entities":{"Q1197028":{"pageid":1207777,"ns":120,"title":"Item:Q1197028","lastrevid":47103568,"modified":"2025-12-31T16:45:23Z","type":"item","id":"Q1197028","labels":{"en":{"language":"en","value":"\\(T\\)-colorings of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 89903"}},"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":"Q1197028$E358765D-87D2-49F3-9394-40E64AD49A79","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0ab19e14438fb29dd70775d3e90496ab89cf1a42","datavalue":{"value":{"text":"\\(T\\)-colorings of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1197028$A53026D6-5B5E-4909-8950-A65DFA74853B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ad4893f67f9a390eef5801576d1d1f8c37a459fb","datavalue":{"value":"0779.05021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197028$F9FDA239-2D1F-4DB5-B1C5-B7093B4B5F10","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ae4f4aef4d5d10f0ed33b50809299ddbc6fa08e3","datavalue":{"value":"10.1016/0012-365X(92)90603-D","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197028$33F8B58A-1A0B-4B1F-8E74-E63F7EB9B7B1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"18bb92565d9f2b332ec88013cd5ad6d4fda0b889","datavalue":{"value":{"entity-type":"item","numeric-id":189455,"id":"Q189455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197028$7867A38D-DE2A-4224-8B67-BE392AF5078F","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":"Q1197028$4ECC70AC-B92F-4B73-900E-A859A91E8767","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1197028$AAEEF373-36D2-4EB1-BDE6-74CAC322D546","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21391a3e8e0199778d68ecbacbec19fa95c06350","datavalue":{"value":"Given a finite set \\(T\\) of natural numbers containing 0, a \\(T\\)-coloring of a simple graph \\(G=(V(G),E(G))\\) is a function \\(f\\) from the vertex set \\(V(G)\\) to natural numbers such that \\(| f(u)-f(v)|\\notin T\\) whenever \\(\\{u,v\\}\\in E(G)\\). The span of a \\(T\\)-coloring is defined to be the difference between the largest and smallest color used. The \\(T\\)-span of \\(G\\), denoted by \\(\\text{sp}_ T(G)\\), is the minimum span among all \\(T\\)-colorings of \\(G\\). A graph \\(G\\) is weakly perfect if the chromatic number \\(\\chi(G)\\) is equal to the clique number \\(\\omega(G)\\). A special graph \\(G^ n_ T\\) plays an important role in this paper. The vertex set of \\(G^ n_ T\\) is \\(\\{0,1,2,\\ldots,n-1\\}\\) and \\(\\{u,v\\}\\in E(G^ n_ T)\\) if and only if \\(| u-v|\\notin T\\). The main theorem shows that, given \\(T\\), the following are equivalent: (i) \\(\\text{sp}_ T(G)=\\text{sp}_ T(K_{\\chi(G)})\\) for all graphs \\(G\\), (ii) \\(\\text{sp}_ T(G^ n_ T)=\\text{sp}_ T(K_{\\chi(G^ n_ T)})\\) for all \\(n\\), (iii) \\(G^ n_ T\\) is weakly perfect for all \\(n\\). Using these equivalences, known results about sets \\(T\\) which satisfy (i) are derived with shorter proofs. New families of sets \\(T\\) with this property are also constructed. Finally, it is established that \\(\\text{sp}_ T(G)=\\text{sp}_ T(K_ m)=n-1\\) for all graphs \\(G\\) with \\(\\chi(G)=m\\) if and only if \\(\\omega(G^ n_ T)=\\chi(G^ n_ T)=m\\) and \\(\\chi(G_ T^{n-1})<\\chi(G^ n_ T)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197028$D94CDAD4-AD4E-40E5-B950-F72F981384BB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197028$1D90DF60-FB34-43FA-A29A-7D77BB8ACEAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197028$1E570E08-3F1A-4E32-B665-9B5E7A9A1228","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"19b10c1520425234d27d3f7fd1e42c6567178072","datavalue":{"value":"89903","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197028$7B0AA181-D631-411F-80C2-93E91175F1B5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197028$9B559568-F691-42E2-BFB5-B3A06A776659","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197028$2E812D74-C631-461C-B1EC-8B12090920F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb2169375ebb26ec0067c3fe2ae2119dcb9b464e","datavalue":{"value":"clique number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197028$31C695AE-D746-4388-A121-6C64E7A00538","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00506f7b0ca81f2bdddf74b2ae25f283b9601a56","datavalue":{"value":"weakly perfect","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197028$60530C1E-3828-4A76-8F94-D44D67AE80B3","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":"Q1197028$0BA45984-0A8B-418B-B376-389DB084E1B9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c26c0e8ab719150b99b971f6f16d3f7da40826d","datavalue":{"value":{"entity-type":"item","numeric-id":3322121,"id":"Q3322121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197028$E235ED36-A2E6-49A1-B08B-5055B69F8044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4d98b1ff8a95acec1e12dac2f68feea66460460","datavalue":{"value":{"entity-type":"item","numeric-id":3348926,"id":"Q3348926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197028$0DF3F5B6-0229-4BA9-AB90-FF357DE009C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7c22dfd08ecb392ffadfe991dd9437abae46a10","datavalue":{"value":{"entity-type":"item","numeric-id":4731201,"id":"Q4731201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197028$FB51B979-4C06-4FDB-80D5-12F1DA321F9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec8a81cada7474ab919ecd37336c3575eb78e0c9","datavalue":{"value":{"entity-type":"item","numeric-id":3032266,"id":"Q3032266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197028$7426C511-85DC-4939-9955-4CAC64EF8D00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b048e550daccef3ab3d36df1ef2635b07519043","datavalue":{"value":{"entity-type":"item","numeric-id":1309815,"id":"Q1309815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197028$BB621781-6390-4DBF-A921-F53AC6667E3A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"36aa46d3309a4011812955bbb9044f110feda6d5","datavalue":{"value":"https://doi.org/10.1016/0012-365x(92)90603-d","type":"string"},"datatype":"url"},"type":"statement","id":"Q1197028$4ADE2CA3-331F-4AAE-8C16-E4EEA1D50AFE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9e11e5be4663e655949b34bb01a2f77aea82e3d5","datavalue":{"value":"W2005080911","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197028$E7754A48-F5EA-443D-9D74-049F50A16679","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d95f91427b6e2518bf837f124eb71f25f5ca524","datavalue":{"value":{"entity-type":"item","numeric-id":4863459,"id":"Q4863459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02e705dfb2e9b204822271c83bd81efe197b279d","datavalue":{"value":{"amount":"+0.8753414154052734","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":"Q1197028$2CB7E6D4-BC94-4213-BE6C-5F0CE3D95843","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c11d4591963959f9412a7159658d87ba2315b8f8","datavalue":{"value":{"entity-type":"item","numeric-id":3487366,"id":"Q3487366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61deaae40dfc0cf0534f86aa8c34e7bd3a16fc67","datavalue":{"value":{"amount":"+0.8721880912780762","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":"Q1197028$6830A2B3-DB12-4268-9E3A-8FE12FE430BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d00117b7b4e13cc6717e571a27e997220b7f0739","datavalue":{"value":{"entity-type":"item","numeric-id":1356423,"id":"Q1356423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4506314705923f398571eb2ec0333baae83c4fd3","datavalue":{"value":{"amount":"+0.8558731079101562","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":"Q1197028$1CA3844B-6094-48FC-9A19-C54B52ED59BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"224a57ae614d483d57e0b69fa55abe7e50d4c32d","datavalue":{"value":{"entity-type":"item","numeric-id":1918544,"id":"Q1918544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14e867e39f266fd9ea75520798754ef418cad3dc","datavalue":{"value":{"amount":"+0.8526424765586853","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":"Q1197028$AF670776-ED9F-4514-8ECB-113E3DB724AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84a6b3264b0434803c581c832b057856127b8887","datavalue":{"value":{"entity-type":"item","numeric-id":2630781,"id":"Q2630781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4326a79640da6bce82c7466b99a04ea9dd8e11af","datavalue":{"value":{"amount":"+0.8516989946365356","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":"Q1197028$0A02F756-FDC4-491C-BA8D-5B101D61B459","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1197028","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1197028"}}}}}