{"entities":{"Q2508412":{"pageid":2519155,"ns":120,"title":"Item:Q2508412","lastrevid":44232660,"modified":"2025-11-21T03:04:16Z","type":"item","id":"Q2508412","labels":{"en":{"language":"en","value":"Coloring fiber product of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5063017"}},"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":"Q2508412$6819D8F9-919D-4806-A4E1-A287892F0C31","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"51ddd44bd216ddf6456e5a86e076d4311abdfaa9","datavalue":{"value":{"text":"Coloring fiber product of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2508412$344E9584-7122-4267-8052-9147D2227958","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ff8c41aa5cc3017f35f3df3253406ad4f56a8a2b","datavalue":{"value":"1105.05023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2508412$75395B5F-6C7E-4F8B-BA57-CD70E52996B6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d67c7e39b7568897facfc3ef6bc6a5c65d4e52e8","datavalue":{"value":{"entity-type":"item","numeric-id":2508411,"id":"Q2508411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508412$90992F30-24F6-41A5-84C5-27B142D8BA70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"692ce2048991e39aaf8d5623dc50cd220956e79b","datavalue":{"value":{"entity-type":"item","numeric-id":189438,"id":"Q189438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508412$D4BBDF1E-902A-4AE7-859A-5C12C61A7192","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0c4f4c12fba9a42c30c78290c58550d441d5b3a7","datavalue":{"value":{"entity-type":"item","numeric-id":801929,"id":"Q801929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508412$F1A2DDCE-2BE6-47B8-B955-93EEEC451FB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4e030767a7bc7157f1fa57ca753ab8dc4f7c3535","datavalue":{"value":{"entity-type":"item","numeric-id":2488841,"id":"Q2488841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508412$35A15772-25DA-4D41-B15C-ECC63950F1B3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"03e0344fac3b71001f7d01722f599a45a6c3dae0","datavalue":{"value":{"entity-type":"item","numeric-id":321980,"id":"Q321980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508412$1762D640-10C8-4C4D-999E-6E73834B6306","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"878e492743d59f168de33092ec560f832c2dc226","datavalue":{"value":{"time":"+2006-10-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2508412$2EFF1FD2-EF69-491C-8FDC-A0A8A8EA4A14","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a4bc8dd3635e820c988a5cd021de2ef387795d14","datavalue":{"value":"The cross product \\(G_1\\times G_2 = (V,E)\\) of two graphs \\(G_i=(V_i, E_i)\\), \\(i=1,2\\), consists of \\(V=V_1\\times V_2\\) and \\(E=\\{(u_1, u_2)(v_1, v_2) \\mid u_1v_1\\in E_1\\) and \\(u_2v_2\\in E_2\\}\\). A homomorphism \\(f: G\\rightarrow H\\) of two graphs \\(G\\) and \\(H\\) is a mapping from the vertex set of \\(G\\) into the vertex set of \\(H\\) such that \\(f(u)\\) and \\(f(v)\\) are adjacent in \\(H\\) whenever \\(u\\) and \\(v\\) are adjacent in \\(G\\). Given \\(H, G_1, G_2\\) and homomorphisms \\(f_i: G_i\\rightarrow H\\), \\(i=1,2\\), the fiber product (over \\(f_1\\) and \\(f_2\\)) \\(G_1\\times_H G_2 =(V, E)\\) consists of \\(V=\\{(u_1, u_2)\\in V_1\\times V_2 \\mid f_1(u_1) = f_2(u_2)\\}\\) and \\(E=\\{(u_1,u_2)(v_1,v_2) \\mid u_1v_1\\in E_1\\) and \\(u_2v_2\\in E_2\\}\\). Thus, \\(G_1\\times_H G_2\\) is an induced subgraph of \\(G_1\\times G_2\\).  Hedetniemi conjectured that \\(\\chi(G_1\\times G_2) > n\\) whenever \\(\\chi(G_i) > n\\), \\(i=1,2\\). A stronger conjecture by Khelladi reads as follows: For any homomorphisms \\(f_i:G_i\\rightarrow K_n\\), \\(\\chi(G_1\\times_{K_n} G_2)\\leq n\\). The authors prove the latter for \\(n\\leq 3\\). They also prove that the following conjectures are equivalent:  Conjecture A: For any graphs \\(G_i\\) with \\(\\chi(G_i) > n\\), \\(i=1,2\\), and \\(p\\geq\\max\\{\\chi(G_1),\\chi(G_2)\\}\\), there exist homomorphisms \\(f_i: G_i\\rightarrow K_p\\) such that \\(\\chi(G_1\\times_{K_p} G_2) > n\\).  Conjecture B: If \\(\\chi(G)>n\\), then for every homomorphism \\(f: G\\rightarrow K_p\\) with \\(\\chi(G)=p\\), \\(\\chi(C_n(G,f))=n\\), where \\(C_n(G, f)\\) is the graph with vertex set  \\[ A_1\\cup\\cdots\\cup A_p,\\quad A_i =\\{\\varphi \\mid \\varphi:f^{-1}(i)\\rightarrow K_n\\},\\quad 1\\leq i\\leq p, \\]  and edge set  \\[ \\{\\varphi\\varphi' \\mid \\varphi\\in A_i, \\varphi'\\in A_j, \\text{ and for all }(u,v)\\in f^{-1}(i)\\times f^{-1}(j),\\;uv\\in E(G)\\text{ implies }\\varphi(u)\\not=\\varphi'(v)\\}. \\]  Note that Conjecture A implies Hedetniemi's conjecture (and hence so does Conjecture B).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2508412$7C02746D-0A76-4E93-BA1C-A4AD60782170","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c4d08f81dccf0def423a8aaa09abdd52c85c61ef","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508412$F5E5796D-4FD5-4738-8004-FBF732392AB7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2508412$ACE7DE6A-F8F6-446C-8467-1ABC936DD7F5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fd3ed6200d40bda242fcb86bc37676ba861a5f94","datavalue":{"value":"5063017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2508412$AD39CBA6-1380-4B0C-94F6-3DAD4FABD973","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"600bbb06e97e6606c9effff6f2c763b132036bec","datavalue":{"value":"Hedetniemi's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2508412$F3B2C0CF-8CAB-4DA9-902F-E074ED9AE858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2508412$3B763881-056E-4446-BD2E-21C0D8F15301","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":"Q2508412$D935AEAD-A0BF-4DAC-9C53-2C12D1A17D66","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"837b316afa9add6e816b0292c17eb549c4b5af66","datavalue":{"value":{"entity-type":"item","numeric-id":3128559,"id":"Q3128559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8f4ae8b5825fb0ad371f24fad9bc51b5c4c4077","datavalue":{"value":{"amount":"+0.922851","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508412$4AA5691D-E871-4FD9-8E65-AC3262EA8A4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e6845c0e2fd11689dd9a2a7da54be94abd0a3e5","datavalue":{"value":{"entity-type":"item","numeric-id":1743686,"id":"Q1743686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2807f38614d99ac94a7451ebf56f6f2eab223531","datavalue":{"value":{"amount":"+0.90805966","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508412$74FE1498-31B4-482F-8CDB-21F2418C5184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"032737db3ee66225d7e28958e02c7a42ccb90aa6","datavalue":{"value":{"entity-type":"item","numeric-id":327644,"id":"Q327644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6c30115d34655a4caa4a470768ff8d199b4f429","datavalue":{"value":{"amount":"+0.90375125","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508412$DE500C05-6A6D-4FBD-B4A5-DB451F02DB91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9dac0936beea08613194377f2c42d9d84398237e","datavalue":{"value":{"entity-type":"item","numeric-id":4715283,"id":"Q4715283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8963da3d1720a50b0d9ba2e05d05cc1ee53b4cd5","datavalue":{"value":{"amount":"+0.8995585","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508412$488D2D7B-3C89-40FB-82A6-CA2AECF0EBF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f285a96cab623e129e8b9978fc29bbe7b5bfb7b","datavalue":{"value":{"entity-type":"item","numeric-id":1923489,"id":"Q1923489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68cedffa363415bf5e9e6d9e772b4bcbc12b5d7d","datavalue":{"value":{"amount":"+0.8995287","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508412$039B0D3C-FEB4-4CD0-B37B-8F1BE31F2DE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"826433a0880ec5c2da6ad8dccc12ae7bbc3734cb","datavalue":{"value":{"entity-type":"item","numeric-id":2368384,"id":"Q2368384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea98157b23064dd2a6a496ed234836e8b72a26c5","datavalue":{"value":{"amount":"+0.8963163","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508412$0D731D9D-8DBA-4E57-8000-6B7071EB2C0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d5833ef827d41052d8009d9d62424262c74c88b","datavalue":{"value":{"entity-type":"item","numeric-id":1683564,"id":"Q1683564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b49e20d31f708fbc979d964f9805e00205711e6","datavalue":{"value":{"amount":"+0.89507806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508412$5C5820E2-70A7-446C-A513-2D0D728DB031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35d80f50a6ead9f0fcf7b1bd1342b04f045aed31","datavalue":{"value":{"entity-type":"item","numeric-id":5063281,"id":"Q5063281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac677491dd7279aea40d5512d67b3c7860e30fe5","datavalue":{"value":{"amount":"+0.89258456","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508412$B4E673B1-6CE8-4AD0-AF00-A1A66E0E09C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c38187ea9406ce08bc2271f0862bb1a381abf8ea","datavalue":{"value":{"entity-type":"item","numeric-id":1683530,"id":"Q1683530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d469feaed6aa65970fcc1454779f482d90b37c05","datavalue":{"value":{"amount":"+0.89160395","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508412$157BDCE2-B1B5-4337-9585-57D18F051106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ee28cd6cd6dfad7771968e71d54e285beff7017","datavalue":{"value":{"entity-type":"item","numeric-id":3686733,"id":"Q3686733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57303c18914f55958fa66fdd04eac25e6ad15548","datavalue":{"value":{"amount":"+0.8907082","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508412$25AE325B-3DA1-455E-A210-7214300F273E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2508412","badges":[]}}}}}