{"entities":{"Q5957752":{"pageid":8134554,"ns":120,"title":"Item:Q5957752","lastrevid":47758999,"modified":"2026-01-02T15:07:04Z","type":"item","id":"Q5957752","labels":{"en":{"language":"en","value":"On the divisibility of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1719007"}},"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":"Q5957752$F74D5EED-06F3-46D0-AE3C-E3B70AE36D6B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dcf7d4c6efd36c6603d5876f0c5eecd22419dd51","datavalue":{"value":{"text":"On the divisibility of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5957752$A08ED413-B551-4741-B243-C1C58269DFA9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a6976425570fd9b3b8c1987837912df1ed5ee8bc","datavalue":{"value":"0988.05068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5957752$E2BDAE9D-1A87-4461-8706-20743746BE7E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"baeeef1b476a030ebb0b3482621189e5b125ccdd","datavalue":{"value":"10.1016/S0012-365X(01)00054-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5957752$CE34E618-C7CA-4436-A1FF-1AFBAC89FB25","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7598b946dc98bf1d17807d2ef3a244f2419361f8","datavalue":{"value":{"entity-type":"item","numeric-id":234396,"id":"Q234396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5957752$260AA80D-6959-4074-A706-40EF49221D9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"03f08a3cbc69e48052a97dab7b19fd1cbcee9fe9","datavalue":{"value":{"entity-type":"item","numeric-id":1227010,"id":"Q1227010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5957752$76B83C05-4BF4-4774-9ECE-777B20B90601","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":"Q5957752$509FF4E4-E41D-4378-AA8B-C6212C75BC05","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1bdd63e74125a64b52265510548f082cbef9c284","datavalue":{"value":{"time":"+2002-06-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5957752$39E455BE-0A76-4230-A224-94E1F10DEA38","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5957752$6E963526-1266-4722-BADC-73A8B20368E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5957752$43B7F05A-750E-4F1F-B054-EBBAFD7C7009","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5957752$4A1C7ED9-822E-4ED4-BEA4-BC1C39B3EDF6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9cb78c8861c095610161c3f6b0cc9b4eb22c5e6d","datavalue":{"value":"1719007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5957752$1DA13FB9-43ED-45B8-8C98-15C4BB185344","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9b194623b94c68e817528a2366db86f33f73962","datavalue":{"value":"divisibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q5957752$EDF7E797-6406-460E-9102-0867D58FBBBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2678790d3652420f5b7224a6923996496d1c5d99","datavalue":{"value":"cricket","type":"string"},"datatype":"string"},"type":"statement","id":"Q5957752$7C9F1E5D-D601-4E25-A3DF-480064871567","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f3c2083c5ecd760f29a0fd2c8804f62d7b64626","datavalue":{"value":"cricket-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5957752$618A0C1F-14EA-4B9B-A6E8-6A225DAD187F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f596663b759fe66d43e2c71438b5b73af575ec04","datavalue":{"value":"diamond-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5957752$D22B09AB-488A-4B52-B3FF-38F1CEF17FD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a11116a6b4821127d46d686f666f969b50e0a4e","datavalue":{"value":"strong perfect graph conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q5957752$BD691F89-EF71-4E6D-B956-A5BF4EE87102","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":"Q5957752$A3A040F3-8EDA-4818-991B-97153D9D058D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ef38d16b58c7634af42205e021ecec0e5e9a3f95","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(01)00054-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q5957752$37018D0C-B093-499E-99CB-E34A4A2FEFBB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3ec5b759876fb1d492f1fdb01ec42f75c0c4119f","datavalue":{"value":"W1992400796","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5957752$77921AB2-8191-4C45-9CC6-0DEBD19AEA1F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"243e829f9ba6a70eb48bbd412550694e723abe73","datavalue":{"value":"For a simple graph \\(G=(V,E)\\) and a vertex \\(x \\in V\\), let \\(H_1,H_2,\\ldots ,H_k\\) be the \\(k\\) \\((\\geq 1)\\) components of the neighborhood \\(N(x)\\) of \\(x\\) in \\(G\\). Then the graph \\(G_x\\) is obtained from \\(G\\) by the transformation of removing \\(x\\) and adding \\(k\\) new non-adjacent vertices \\(x_1,x_2,\\ldots ,x_k\\) (called copies of \\(x\\)) and making each \\(x_i\\) adjacent to all vertices in \\(H_i\\) \\((1\\leq i \\leq k)\\). In the resulting graph \\(G_x\\), the neighborhood of each copy \\(x_i\\) of \\(x\\) is connected. Using this transformation repeatedly one gets a graph \\(\\widetilde{G}\\) in which no vertex has a disconnected neighborhood. The construction of \\(\\widetilde{G}\\) takes \\(O(|V|^2+ |V||E|)\\) time and \\(\\omega(G) = \\omega (\\widetilde{G})\\), where \\(\\omega \\) is the clique number. NEWLINENEWLINENEWLINEA cricket is the graph consisting of a triangle with two pendant edges at one vertex of the triangle. The authors prove that for a cricket-free graph \\(G\\) without odd holes, \\(\\chi (G) \\chi (\\widetilde{G})\\), where \\(\\chi \\) is the chromatic number. NEWLINENEWLINENEWLINEA gem is \\(K_1 \\vee P_4\\) and let \\(F_1\\) be the graph obtained by identifying an edge of \\(K_4\\) with an edge of another \\(K_4\\). The authors prove that the clique number of \\((\\text{gem},F_1)\\)-free graphs can be computed in \\(O(|V|^2+|V||E|)\\) time. This class strictly contains the diamond-free graphs. They further deduce the validity of the strong perfect graph conjecture (SPGC) for (cricket, gem, \\(F_1\\))-free graphs. NEWLINENEWLINENEWLINELet \\( F_2 = K_2\\vee \\overline{K}_3,\\;F_4 = K_1\\vee P_5\\) and \\(F_3\\) be obtained by identifying two adjacent edges of a \\(K_4\\) with an edge each of two different triangles. All these graphs and the cricket contain a claw. The authors prove that the SPGC is true for \\((\\text{cricket},F_2,F_3,F_4)\\)-free graphs, thus extending the result for claw-free graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5957752$59D0E4E4-B371-4A01-8BCA-C54402B2702E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44ac640b72bb89f64cce4c2fcdafdc0b1d3b60fd","datavalue":{"value":{"entity-type":"item","numeric-id":1850572,"id":"Q1850572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06cc66ddae8000c6ed6e356e67fef6d293b9a37c","datavalue":{"value":{"amount":"+0.8492922782897949","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":"Q5957752$A02C9890-E487-4DCF-8B92-898B305E73F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3656a9163c7fe3291c6ad2ed19fc3c0dec04273","datavalue":{"value":{"entity-type":"item","numeric-id":2144602,"id":"Q2144602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61c87960f4e54e436e089c790438a17f848e0c52","datavalue":{"value":{"amount":"+0.7957326173782349","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":"Q5957752$0979EDBB-F627-4BEA-B3C6-BE9DAF7DD2DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b26c956ce4a81a91cefbb2459fb043924e1d09ac","datavalue":{"value":{"entity-type":"item","numeric-id":2918532,"id":"Q2918532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"932213296c6f47267cd814094c84deaef51543ae","datavalue":{"value":{"amount":"+0.7939090728759766","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":"Q5957752$43986792-8E53-49A2-9702-6B84F4644096","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc20b62cb9c6b85fbe0b1784833623ce37018561","datavalue":{"value":{"entity-type":"item","numeric-id":5903942,"id":"Q5903942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"188c38678e8572cdc14f24e1b720e9a939c497d0","datavalue":{"value":{"amount":"+0.7889775633811951","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":"Q5957752$D435F40B-BA04-4A1B-932E-41F705FF600F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"294b86cacba0294014f6420efa4898597892e71c","datavalue":{"value":{"entity-type":"item","numeric-id":1112848,"id":"Q1112848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27eb26017d6726654f5a59370b4bf27f565a2c40","datavalue":{"value":{"amount":"+0.7870844006538391","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":"Q5957752$7CD87EED-3D9A-46A1-AE19-062402A10A30","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5957752","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5957752"}}}}}