{"entities":{"Q1801332":{"pageid":1812074,"ns":120,"title":"Item:Q1801332","lastrevid":69169005,"modified":"2026-04-13T05:13:52Z","type":"item","id":"Q1801332","labels":{"en":{"language":"en","value":"Strong products of \\(\\chi\\)-critical graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 202378"}},"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":"Q1801332$033717A8-E33A-48D8-88AE-63BE1B0513E4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6fbbf046f6f94ffb1560de4c4797d6122c7479ed","datavalue":{"value":{"text":"Strong products of \\(\\chi\\)-critical graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1801332$8F644CA2-0238-47AA-A636-067F81E3A941","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"40a1b49f66b618cdc78b82950f06265731b0e8b5","datavalue":{"value":"0787.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801332$2B8C7FC8-D771-47B6-A9DF-2F9AF1551AC2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"48546b7af384eb20f0a5dcdb8f7be89f6d96e15e","datavalue":{"value":"10.1007/BF01855874","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801332$85FEE40A-0553-47B8-9761-97A4EA506A66","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ceb1fcf1c75dc367d934ec93f0fd1abaa5c7756","datavalue":{"value":{"entity-type":"item","numeric-id":251101,"id":"Q251101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$B345E054-53B8-4BA0-B60C-A1BB6D26A48E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2e8211cf89fb3e58cebf657950368971306be793","datavalue":{"value":{"entity-type":"item","numeric-id":176881,"id":"Q176881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$98346259-D789-4CB5-80F4-9E351D22582F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7a2ae337094f9b29ef7d03c29f436d8f988b84f0","datavalue":{"value":{"time":"+1994-05-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1801332$6D843AD3-DE7C-4639-8180-C2B4CBEDE497","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f5c9c1373837af1e90527afff95fe0ad2fb9a166","datavalue":{"value":"https://eudml.org/doc/137517","type":"string"},"datatype":"url"},"type":"statement","id":"Q1801332$CEBEBADC-9070-4238-B789-DDB1788F2595","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"56f96406da519c8a549bd241d8b8b8d8fdc25e89","datavalue":{"value":"For a (finite, undirected, simple) graph \\(G= (V(G),E(G))\\), let \\(\\alpha(G)\\), \\(\\omega(G)\\), \\(\\chi(G)\\) denote the independence number, clique number, chromatic number, respectively. The lexicographic product and the strong product of graphs \\(G\\) and \\(H\\) are denoted by \\(G[H]\\) and \\(G\\otimes H\\), respectively, and the least integer \\(\\geq x\\), \\(x\\in R\\), by \\(\\lceil x\\rceil\\) (unfortunately, more than once also written as \\([x]\\) in the paper). The main result is that  \\[ \\chi(G\\otimes H)\\leq \\chi(G[H])\\leq (\\chi(G)- 1)\\chi(H)+\\left\\lceil{\\chi(H)\\over \\alpha(G)}\\right\\rceil \\]  holds for any graph \\(H\\) and any critical (with respect to vertex colouring) graph \\(G\\). As an interesting corollary it follows that if \\(G\\) has a retract which is critical and not complete, then \\(\\chi(G[H])<\\chi(G)\\chi(H)\\) for every \\(H\\) with \\(E(H)\\neq\\varnothing\\). Furthermore, the main result is used to calculate the chromatic numbers for some strong products, namely \\(\\chi(\\overline C_{2k+1}\\otimes K_ n)= kn+\\Bigl\\lceil{n\\over 2}\\Bigr\\rceil\\) \\((k\\geq 2, n\\geq 1)\\), \\(\\chi(C_ 5\\otimes C_ 5\\otimes C_{2k+1})=10+\\Bigl\\lceil{5\\over k}\\Bigr\\rceil\\) \\((k\\geq 2)\\), \\(\\chi((G+H)\\otimes K_ n)=\\chi(G\\otimes K_ n)+\\chi(H\\otimes K_ n)\\), \\(\\chi((K_{n-3}+ C_ 5)\\otimes K_ m)= (n- 1)m+\\Bigl\\lceil{m\\over 2}\\Bigr\\rceil\\) \\((n\\geq 3, m\\geq 1)\\), where \\(G+ H\\), \\(\\overline G\\), \\(C_ n\\) and \\(K_ n\\) denote the join of \\(G\\) and \\(H\\), the complement of \\(G\\), the cycle of length \\(n\\), and the complete graph on \\(n\\) vertices, respectively.   That the upper bound for \\(\\chi(G\\otimes H)\\) in \\(\\chi(G\\otimes H)\\leq \\chi(G)\\chi(H)\\) cannot be improved for non-critical graphs \\(G\\) with \\(\\omega(G)<\\chi(G)\\) is shown by the construction of two sequences of graphs \\(G^ k_ n\\), \\(n=1,2,\\dots\\), for \\(k= 2\\) and \\(k= 4\\) satisfying \\(| V(G^ k_ n)|= (3k+ 2)n\\), \\(2= \\omega(G^ k_ n)< \\chi(G^ k_ n)= 3\\), and \\(\\chi(G^ k_ n\\otimes K_ k)= 3k= \\chi(G^ k_ n)\\chi(K_ k)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801332$1A53D6B2-3087-4B25-8190-5F3611061382","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801332$09BD1A1D-774D-4EC9-9129-56728051C9C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801332$D99072E3-2F2C-4F07-B6A4-507E80364D08","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cf32fa473414cda90663579705f61f6ecd0ca489","datavalue":{"value":"202378","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801332$22DF0C39-10AE-48D9-BB68-133ECFAE13E7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a058c07e6706bc87ea32b0f7358b90fb65e896e","datavalue":{"value":"critical graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801332$FD04F4E9-E691-4DFE-9F14-F216F27AF0E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b89aa1b9eed71217ebf6a719487a219071558409","datavalue":{"value":"independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801332$D4FF0FD1-FF79-4F54-A869-09E93AFE5B16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb2169375ebb26ec0067c3fe2ae2119dcb9b464e","datavalue":{"value":"clique number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801332$E20B8283-B2C3-43B0-B2B0-377D3E129EB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801332$E373C988-F626-49F9-812E-61E814AD392C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"200b0f187ad1b101c5ee111f093a447fdd14368b","datavalue":{"value":"lexicographic product","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801332$55D67FA3-C775-4512-86D8-FBAB9E2FBCCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a31bab31ace781abe03a0ec8976d4f544b40f43","datavalue":{"value":"strong product","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801332$E19B8C34-5E8F-452E-A02F-F06BF30FD705","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50328b331aa4cde61eb0cba86d225c9cec8ba382","datavalue":{"value":"retract","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801332$A8315E31-7B89-48DD-BAC6-4ED5E2F1F139","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ab25d4f22422fef1c0f819f04a582c1dc09a95d9","datavalue":{"value":{"entity-type":"item","numeric-id":878647,"id":"Q878647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$F847BB5A-4C74-4183-A119-E3F0C67AE39F","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":"Q1801332$9C828D4B-1813-46BA-83C7-B5B7C6589450","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f268cfcd12ecfd4de0cebd3c52b6a3a1aa4de0b","datavalue":{"value":{"entity-type":"item","numeric-id":1210332,"id":"Q1210332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$84512305-E414-49D3-9671-DAAF2B6FABCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d111ed39e76e06afda08706f554c998997c48f2","datavalue":{"value":{"entity-type":"item","numeric-id":4710541,"id":"Q4710541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$31681E4F-EDCF-4648-9559-AB5C894BE8EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5e21a0d2f846c7b5db53c68e1a2923e4c158d6a","datavalue":{"value":{"entity-type":"item","numeric-id":1067411,"id":"Q1067411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$82B1B5F1-CEAE-4D8F-8660-3A338DE9C4A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c25249474734f117fbdf2b2d4cabcd088103c2e","datavalue":{"value":{"entity-type":"item","numeric-id":686286,"id":"Q686286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$6F6C7574-F2B8-49FA-8092-DC6A16316997","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82bd142382c48198bd3d062596f9da54dc955038","datavalue":{"value":{"entity-type":"item","numeric-id":1230631,"id":"Q1230631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$2E130EEC-58FA-4969-AD4C-36612200BEB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67f29bec88daf336d76f38f176d5988388118c07","datavalue":{"value":{"entity-type":"item","numeric-id":3697031,"id":"Q3697031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$DD0C2DDA-D4A2-42A7-B1B3-AC9D10499203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2df0f2f5bef9f5f6d06209f883d0e5c47a62e460","datavalue":{"value":{"entity-type":"item","numeric-id":686295,"id":"Q686295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$68EA9AAD-2254-4BF3-A1EC-F4F6B456D347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bf253969479d7db395bb06198c49f7849f3804e","datavalue":{"value":{"entity-type":"item","numeric-id":686296,"id":"Q686296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$5F06475A-3070-4F84-9115-FC714ED3F2E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd3d4e1af97cbca7e3cbe4b7cc3210fb8a7810d1","datavalue":{"value":{"entity-type":"item","numeric-id":912867,"id":"Q912867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$74778594-A2E5-42D7-A31A-B95432271A54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beebddf937b5d723f8911daf0b45941cb0d5d03d","datavalue":{"value":{"entity-type":"item","numeric-id":5525913,"id":"Q5525913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$434B8D9D-E151-42FA-80A5-B688CD25C1B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4364a0dd6a91eabbb48c8eca3a979e6b696b8b62","datavalue":{"value":{"entity-type":"item","numeric-id":5905719,"id":"Q5905719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$9839FA43-E079-4F86-B452-EB09A598F264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81dd3d69aa7c63b7fddac93f5f2238038a25e34b","datavalue":{"value":{"entity-type":"item","numeric-id":4180378,"id":"Q4180378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$01C8C3A8-E1AD-4F90-97A1-D9CB153A24C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e66745683a254e2edeba94d632f188e0e8c06f9","datavalue":{"value":{"entity-type":"item","numeric-id":1110526,"id":"Q1110526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$27376A63-5790-4655-824C-25185C19BDA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30ee28d0ed23e167ceb3fdd62454860bee3279de","datavalue":{"value":{"entity-type":"item","numeric-id":579285,"id":"Q579285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801332$D0C5B2B0-0F13-4859-AED6-12C929A349B4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f6a65f489e8c1476725485af0f4f34071b0e57e6","datavalue":{"value":"W4250749033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801332$09FEBA00-46F3-466A-8118-308CFD415FA0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d029676e22264bb2a2b4b734bb5ecb13fbf09a5","datavalue":{"value":{"entity-type":"item","numeric-id":1336712,"id":"Q1336712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86fbb1d128a7bcc49405f2a7637f87acc81d8772","datavalue":{"value":{"amount":"+0.8488612771034241","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":"Q1801332$402FD2E5-9B63-45D7-927B-8932A43EE296","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04790fc781233c74f491be435e126cfcfbe9bddd","datavalue":{"value":{"entity-type":"item","numeric-id":1339858,"id":"Q1339858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"440557029bb380bea31a80ec58a3a5f1c7e1dfc5","datavalue":{"value":{"amount":"+0.8478038311004639","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":"Q1801332$A762094D-79F7-43BA-8BA0-7463922707EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9e58a57dd8891f45c35fb59d64ae601eb10957e","datavalue":{"value":{"entity-type":"item","numeric-id":3410616,"id":"Q3410616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"440557029bb380bea31a80ec58a3a5f1c7e1dfc5","datavalue":{"value":{"amount":"+0.8478038311004639","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":"Q1801332$D3F1F03C-99B4-4D47-B550-14D473072A4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e92ae18f8564a39af0a9b3e2f21714764bfe660d","datavalue":{"value":{"entity-type":"item","numeric-id":3820620,"id":"Q3820620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1983acab0e0ba5330943f0ac2efe661a141660e","datavalue":{"value":{"amount":"+0.8450813889503479","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":"Q1801332$8EB69F9F-062E-4763-BF15-CAE27C84E182","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"961c79402a1d883cfaa3e1fe0dcb429a881186ab","datavalue":{"value":{"entity-type":"item","numeric-id":2717070,"id":"Q2717070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"623db1274daa81d2961c779ec2217c6da796c33f","datavalue":{"value":{"amount":"+0.8286503553390503","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":"Q1801332$6241A483-A891-4DB9-8984-980B463D38C8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Strong products of \\(\\chi\\)-critical graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Strong_products_of_%5C(%5Cchi%5C)-critical_graphs"}}}}}