{"entities":{"Q2413627":{"pageid":2424370,"ns":120,"title":"Item:Q2413627","lastrevid":57898857,"modified":"2026-04-03T00:22:25Z","type":"item","id":"Q2413627","labels":{"en":{"language":"en","value":"Cliques in the union of \\(C_4\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6937374"}},"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":"Q2413627$1F3CD719-72DD-4B61-B164-7FBA1DA1F3C3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cf6984b42bcab12900409f09b3a3d2749b2a6773","datavalue":{"value":{"text":"Cliques in the union of \\(C_4\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2413627$021F8770-39C1-4A68-844F-247ACD7247CC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b2337aa6c3403e650c5a4eb0404552acc53e0557","datavalue":{"value":"1430.05090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413627$1514F7C6-2318-4317-B7E8-087BBAFA45B5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b5ec5eac3eb515c7c35c09d41e4b67ceebac214","datavalue":{"value":{"entity-type":"item","numeric-id":2413626,"id":"Q2413626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2413627$08DE0E22-1440-4679-8F50-81CC647D9831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"84a8555b67c6b23fa0b4b81d144fd117edd2c5b2","datavalue":{"value":{"entity-type":"item","numeric-id":186190,"id":"Q186190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2413627$F47F54DC-01E3-40D7-99E1-B031FF44B0E7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2413627$A8917D04-E2C4-4343-BBBE-3D92452C4F8D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"96991e0a814f7bc32172a45927ca35ab5cd77835","datavalue":{"value":{"time":"+2018-09-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2413627$8CDFD34E-3652-407F-8FC3-773E323748CB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"96eee5d0cd09bf10377ea74a3d75a50256cf06a0","datavalue":{"value":"https://arxiv.org/abs/1511.08772","type":"string"},"datatype":"url"},"type":"statement","id":"Q2413627$F10E92A2-D1BC-4FC2-BD86-DBA1F7D94D2E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aa40edbc93d07a4dc9a77c1d72f6f3423428deab","datavalue":{"value":"A graph \\(G\\) is \\(C_4\\)-free if no induced subgraph of \\(G\\) is isomorphic to the \\(4\\)-cycle. The authors prove that if \\(G\\) is a complete graph with vertex set \\(V\\) that is the union of two \\(C_4\\)-free graphs \\(B\\) and \\(R\\) with the same vertex set, then \\(V(G) = X\\cup Y\\cup Z\\) where \\(X\\) and \\(Z\\) are cliques in \\(B\\), and \\(Y\\) and \\(Z\\) are cliques in \\(R\\). This implies the following inequality relating the clique numbers of these three graphs: \\(|V| = \\omega(G)\\le \\omega(B)+\\omega(R)\\). For general \\(C_4\\)-free graphs \\(B\\) and \\(R\\), the following bounds are proved: \\newline \\(\\omega(B\\cup R)\\le \\omega(B)+\\omega(R)+\\frac{1}{2}\\min\\{\\omega(B),\\omega(R)\\}\\) and \\(\\omega(B\\cup R)\\le \\omega(B)+\\omega(R)+\\omega(B\\cap R)\\).  The motivation for this study comes from Ramsey theory, or, more precisely, from the quest of identifying conditions on pairs of graphs \\(B\\) and \\(R\\) such that every clique in \\(B\\cup R\\) is the union of a clique in \\(B\\) and a clique in \\(R\\). The results in this paper generalize a result of \\textit{A. Gy\u00e1rf\u00e1s} and \\textit{J. Lehel} [Electron. J. Comb. 23, No. 3, Research Paper P3.40, 5 p. (2016; Zbl 1344.05106)] showing that if the edges of a complete graph \\(G\\) are colored with red and blue (both colors can appear on an edge) so that there is no monochromatic induced \\(C_4\\) and there is no \\(K_5\\) on which both color classes induce a \\(C_5\\), then the vertices of \\(G\\) can be partitioned into a red clique and a blue clique.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2413627$15E3C863-204E-4FDA-A772-C7EE14072B77","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"040d69b518efce5903b0eb219fe1ac8c6ab78b7f","datavalue":{"value":{"entity-type":"item","numeric-id":266922,"id":"Q266922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2413627$CFEF2862-4DD2-4950-8D0A-B50A5AD2FDF6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413627$6E1E75D0-B10D-4F7D-994E-EC34013B187F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b4b251e34f965e85a4a30c5d646e0bae1192967","datavalue":{"value":"05D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413627$75B94E6C-7297-4E0D-869C-C2E2CA98CE47","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b45c1ecd6a6a6454f52ecef43ffd2f19af79374a","datavalue":{"value":"6937374","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413627$BDE5E7E6-1DD9-46A4-93F3-DF25CD28AF40","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bfbdacd2237eb430da08e5396101c8d61621d00a","datavalue":{"value":"\\(C_4\\)-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2413627$2F609CF1-5E7F-461D-92A3-33515A2769D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q2413627$72C48D60-31AA-4B93-8195-1B1C60101527","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"951e5da37dd87419be495d53dc2bf254f81e44ef","datavalue":{"value":"obedient set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2413627$0B662632-DB5C-42CA-B0EA-BD2D52A78387","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":"Q2413627$80ADB8AC-E151-48DD-BA81-71FAF5DC4D6F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"192a13233fa165e87f5997f960932ae919982be0","datavalue":{"value":"W2963559438","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413627$8A5D8186-B6EF-4738-8EC5-5032B492BEF1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"99e864c7acb27e21d640d5ee49a7449e2ffbe622","datavalue":{"value":{"entity-type":"item","numeric-id":2349513,"id":"Q2349513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2413627$9D41B823-F29A-4DBE-BD1D-4ADEF14116BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"695d524703bd831d269a56aae2fc788945504906","datavalue":{"value":{"entity-type":"item","numeric-id":2567406,"id":"Q2567406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2413627$4F01BDC1-9C88-446D-AA57-A01609F92195","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bd9ff6961515bb27ca2ac8bd682e908b13759642","datavalue":{"value":"10.1007/S00373-018-1898-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413627$50347DA7-471D-4E73-B603-34F19CDA9943","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01af603da36c4aa2ac854316359fb232336d3a4a","datavalue":{"value":{"entity-type":"item","numeric-id":4379726,"id":"Q4379726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"070dbf2f136d0cc576a016ccf2be68f785f8291d","datavalue":{"value":{"amount":"+0.79954004","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2413627$C720E0E4-8BA1-4092-8951-7912E1B9CCCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eded2097f0c9c2484619965bdcf9e88aade65a21","datavalue":{"value":{"entity-type":"item","numeric-id":3307072,"id":"Q3307072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a930e6e90dc6c91e256a4b6014c3adc2895f584e","datavalue":{"value":{"amount":"+0.79089236","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2413627$1217CE6F-44FB-4E7E-AA23-88C9B58EA8C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4e809c31840fb38f6788ddb38b2135a82882230","datavalue":{"value":{"entity-type":"item","numeric-id":4393350,"id":"Q4393350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0008d58b995f120dfc6d2769b1e1aefee5742211","datavalue":{"value":{"amount":"+0.7825322","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2413627$5B624676-5E96-43E8-B94B-4520D986FB3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ad772e0a8a281b9ee8ef7103e1ef0ffa33a6c2a","datavalue":{"value":{"entity-type":"item","numeric-id":789407,"id":"Q789407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa4fd3ac3e57b101c4c0ffc19474aed823a4316b","datavalue":{"value":{"amount":"+0.7722609","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2413627$E065C774-9CE3-4ECA-8165-34856EFEBA1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a140dc3f3b9ae698d38b6575672a0e665a1f2b3","datavalue":{"value":{"entity-type":"item","numeric-id":510356,"id":"Q510356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cd44e8c59d5c6157ec09a0afbad749563be3aff","datavalue":{"value":{"amount":"+0.7719496","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2413627$94E828D1-825B-4469-94E7-FC15C930A3FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a929ffba207e2f2e10743a6b12dc315df91300b","datavalue":{"value":{"entity-type":"item","numeric-id":271630,"id":"Q271630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b541d6ca3e017b2de79bf883e80c0ba7b12085a","datavalue":{"value":{"amount":"+0.76944965","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2413627$D2CCCA2E-DE6C-403D-9C16-0F932D9FEFD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fcde986a88dae4550653b530f0a59febe0cfc85","datavalue":{"value":{"entity-type":"item","numeric-id":4238172,"id":"Q4238172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccd2f3a762660f771fc2f88c60c4ef9484f7338d","datavalue":{"value":{"amount":"+0.76745653","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2413627$6162FB72-685D-4AC7-87C4-4D5A5BB62E4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76e0f4d0f674ec24869b9c44a07bcad5ee90bdc3","datavalue":{"value":{"entity-type":"item","numeric-id":700383,"id":"Q700383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e189b43779dc7edf7e0c5ed763763f4d81b789f","datavalue":{"value":{"amount":"+0.7644805","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2413627$1D2749FD-2C75-4ACD-AFB1-0E4466076A4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"064dd3728a2fc1b36b374fd2078359f9f2b2e544","datavalue":{"value":{"entity-type":"item","numeric-id":4529454,"id":"Q4529454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9beedfa9db14c745a77a117a35f1b3cf34e30a68","datavalue":{"value":{"amount":"+0.76146317","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2413627$32DFC559-9D30-4C93-B6B5-573A17D90D72","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2413627","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2413627"}}}}}