{"entities":{"Q1339858":{"pageid":1350597,"ns":120,"title":"Item:Q1339858","lastrevid":67190718,"modified":"2026-04-12T15:56:45Z","type":"item","id":"Q1339858","labels":{"en":{"language":"en","value":"On the chromatic number of the lexicographic product and the Cartesian sum of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 701677"}},"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":"Q1339858$70EB6B32-4B5B-40C3-88D6-ED47A8E3553B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ba09a2b4fe46f51cba4c7cb43851a532e07b93b3","datavalue":{"value":{"text":"On the chromatic number of the lexicographic product and the Cartesian sum of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1339858$227565B4-85D5-4CC1-BE8E-7B99EB855D7E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"42c678b78ac907591459590fdd2fc65ec4d516ec","datavalue":{"value":"0815.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339858$BA653EC0-98EF-4D95-907E-20F77B41F0EC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c12bf3c44b975eb42971f3d449c2d6790fb12805","datavalue":{"value":"10.1016/0012-365X(93)E0056-A","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339858$EA2E6DD3-744F-43DC-868E-D39EC6EBDE27","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ec0176bb55b3b35eb124ec9ce3ed3f244d10a06","datavalue":{"value":{"entity-type":"item","numeric-id":1339857,"id":"Q1339857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339858$20BF3F67-39CB-4FF1-9BF5-020924D2710C","rank":"normal"},{"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":"Q1339858$2667DBB0-1C92-4E60-A5F5-EE360D86335B","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":"Q1339858$7A712D16-4156-4E1C-A668-494D7D488E9D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"409ba1216875b3d2fe2760f521e9b8d4dc80e88e","datavalue":{"value":{"time":"+1995-06-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1339858$8BB9B78C-8993-4EF9-82AB-AFA0F22DE693","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ea4b85319500a8728b8e635bf751fdfcc4742936","datavalue":{"value":"Let \\(G\\) and \\(H\\) be graphs. Denote by \\(G[H]\\) their lexicographic product and by \\(G\\oplus H\\) their Cartesian sum, defined by \\(V(G \\oplus H)= G\\times H\\) and \\((a,x)\\sim (b,y)\\) whenever \\(a\\sim b\\) and \\(x\\sim y\\). Some bounds are established on the chromatic number of graphs obtained by the above products: (1) If \\(G\\) is non-bipartite then \\(\\chi(G [H]) \\geq 2\\chi (H)+ \\lceil \\chi(H)/ k\\rceil\\), where \\(2k+1\\) is the length of a shortest odd cycle of \\(G\\). (2) If both \\(G\\) and \\(H\\) are \\(\\chi\\)-critical, but none of them is complete, then \\(\\chi (G\\oplus H)\\leq \\chi(G) \\chi(H) -1\\).    Using these results, the chromatic number of the lexicographic product and the Cartesian sum of any two odd cycles is computed (it is mostly equal to 7 or 8).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1339858$F55BB710-FD60-4862-AFFA-5207F6B3F443","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339858$A2177DE0-12ED-4594-B91A-D964DD8EC1EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339858$5E7C7F97-F31E-4E8E-9B30-EDFFAA4A1C4C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9315afceea789417604830da42c0a01f726dfa9d","datavalue":{"value":"701677","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339858$20D0ECA8-84A8-4AC5-BB81-850504DF10E1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1339858$DBC1157A-9673-4898-9F2C-CD7535F343F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"200b0f187ad1b101c5ee111f093a447fdd14368b","datavalue":{"value":"lexicographic product","type":"string"},"datatype":"string"},"type":"statement","id":"Q1339858$C20DCDD3-8010-4F49-8268-C8C90AB739A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ee34c3c0e942ee39b1fd6e44a841818021aead1","datavalue":{"value":"Cartesian sum","type":"string"},"datatype":"string"},"type":"statement","id":"Q1339858$4A32BCCF-A56E-4F26-BD43-5E28F940DBD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcf267cbc3e04fdcfc3d3761f7ad8ebdabe8c51","datavalue":{"value":"cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1339858$1F790207-BFC4-4BDC-9F88-83C3F31E7CC5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6902b9a56e3d36f68e6c786e52a629adfbe4e237","datavalue":{"value":{"entity-type":"item","numeric-id":234320,"id":"Q234320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339858$398E2BB1-F516-424E-9B1B-E5909F15C1F3","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":"Q1339858$866EDBAA-0DB9-455E-A3DF-29BD203603FA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"85f2d30f47f119ec92e2111e2af3814b88325cb8","datavalue":{"value":{"entity-type":"item","numeric-id":5650700,"id":"Q5650700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339858$FCE5C887-067A-4912-996D-D0D899D8B745","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":"Q1339858$A905F9A0-DF2D-40A8-99F5-3D8F59F4894F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4120bafbef102d43a78cc532543a307c4f4aba37","datavalue":{"value":{"entity-type":"item","numeric-id":1843453,"id":"Q1843453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339858$377AC408-5486-439B-B8C8-D27FA5E76A4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6992a0f0c9c6dd16c2c6d91d9c5dedf2c9b3790f","datavalue":{"value":{"entity-type":"item","numeric-id":3966167,"id":"Q3966167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339858$0E695A5F-1B8E-4DE2-BB79-C2C44448072B","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":"Q1339858$103FD8BB-2831-400D-9C12-4523E505ED14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b63775ab9b3862ddf23540955ffe7ac8b56702aa","datavalue":{"value":{"entity-type":"item","numeric-id":1801332,"id":"Q1801332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339858$21C793FD-CA4E-4B2E-9356-CFCB5BC081E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ad6688e315061cf2331c3d60cb53a128121b095","datavalue":{"value":{"entity-type":"item","numeric-id":1336712,"id":"Q1336712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339858$E90C6A68-539B-4C99-B728-5D08F93A42D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2aa267bacc30ccce8650fc6c0314903585fde889","datavalue":{"value":{"entity-type":"item","numeric-id":3317148,"id":"Q3317148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339858$F09AB324-D41B-4EFC-9305-A6BFC94050FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f88392e2d96e6b20b42940bf56c1735eaf4e5420","datavalue":{"value":{"entity-type":"item","numeric-id":3291034,"id":"Q3291034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339858$1DAD8050-5475-4E16-B1A0-5294ABED9E49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d310a52403762c25d1c62be4475be18d63a73dd","datavalue":{"value":{"entity-type":"item","numeric-id":3820620,"id":"Q3820620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339858$028E8477-9122-4A82-A02F-A0777FCD6A1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bd1435c3b8019d52e6a1caffa9d9c76a380c1d","datavalue":{"value":{"entity-type":"item","numeric-id":1212006,"id":"Q1212006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339858$FF26E672-0AA8-4121-9613-2AB6DB4DEEBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bbe2d527cdb2d07aa02bfde1eddd961e431e4a1","datavalue":{"value":{"entity-type":"item","numeric-id":5540283,"id":"Q5540283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339858$E2EFA8B2-C599-440F-AC6F-C48934F49E1E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3bb66ab61213dbf8581b33c1b6241383c4bcfa9c","datavalue":{"value":"https://doi.org/10.1016/0012-365x(93)e0056-a","type":"string"},"datatype":"url"},"type":"statement","id":"Q1339858$1B609002-F6EF-4E02-A6D2-052C27473ED8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"845c99d452d869efb305cf16b3c68f07c6d4301b","datavalue":{"value":"W2043643906","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339858$9FE2398D-27CA-46F2-AFAA-BD2CFE96A2B5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e19df173b0bda5042b2133668eaa4a6e18a4bd6","datavalue":{"value":{"entity-type":"item","numeric-id":998323,"id":"Q998323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbe77798c73f7387f5b6709a3488db5887a8a583","datavalue":{"value":{"amount":"+0.8543046712875366","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":"Q1339858$43D1F35D-4F9B-40F4-8792-FD924D2277CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d2855f6d9d78e36eb61d660f81105a0e7ad0874","datavalue":{"value":{"entity-type":"item","numeric-id":1801332,"id":"Q1801332"},"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":"Q1339858$C53F5CFE-4D7D-44B1-8976-6A843F4E4C85","rank":"normal"},{"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":"6793dafd05f25b9ea5ba9ab91ec9a5ed0c187dfb","datavalue":{"value":{"amount":"+0.8127654790878296","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":"Q1339858$6AF0CD1A-9B5D-42BA-8A77-105387C5DE2B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the chromatic number of the lexicographic product and the Cartesian sum of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_chromatic_number_of_the_lexicographic_product_and_the_Cartesian_sum_of_graphs"}}}}}