{"entities":{"Q6616437":{"pageid":14227594,"ns":120,"title":"Item:Q6616437","lastrevid":103709987,"modified":"2026-06-06T07:57:53Z","type":"item","id":"Q6616437","labels":{"en":{"language":"en","value":"On the complexity of local-equitable coloring in claw-free graphs with small degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7923966"}},"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":"Q6616437$E034A201-0BAC-4929-8655-C56311FCCBF8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4766a7221e3dd213b4edc659b2f875d8df75800d","datavalue":{"value":{"text":"On the complexity of local-equitable coloring in claw-free graphs with small degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6616437$FC5EAA21-47A0-4D93-8F2E-44EC10D4D115","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"da354ecc142f0dd8ab587d0bc254d2f1ec09e91f","datavalue":{"value":{"entity-type":"item","numeric-id":344542,"id":"Q344542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6616437$AAE32FC2-9996-4DA4-8D14-3EBA79D57C14","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":"Q6616437$00B97213-6A01-427E-B438-89D2FF731D8D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"494bff2bc24699bf535a78d742914a24147db656","datavalue":{"value":{"time":"+2024-10-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6616437$2C6C8AAB-86B3-40B8-9B00-20C406B33C61","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f1ba3c288e771aaf365d78443e684017e2275e68","datavalue":{"value":"Let \\(G\\) be a graph. A set \\(C\\subset V(G)\\) is a clique if the subgraph of \\(G\\) induced by \\(C\\) is a complete graph and a clique is maximal if it is not contained in any larger clique. A map \\(c:V(G)\\rightarrow \\{1,\\dots,k\\}\\) is a \\(k\\)-coloring (where two adjacent vertices can have the same value) and sets \\(V_i=\\{v\\in V(G):c(v)=i\\}\\), \\(i\\in\\{1,\\dots,k\\}\\), are color classes of \\(c\\). A \\(k\\)-coloring is called a local-equitable \\(k\\)-coloring if \\(||V_i\\cap C|-|V_j\\cap C||\\leq 1\\) for every maximal clique \\(C\\) and any \\(i\\leq i<j\\leq k\\).\\N\\NA complete bipartite graph \\(K_{1,3}\\) is called a claw and a graph \\(G\\) is claw-free if \\(G\\) posses no induced subgraph isomorphic to a claw.\\N\\NThis contribution is a study of claw-free graphs with maximum degree of at most four with respect to local-equitable \\(2\\)-coloring. In particular, a linear algorithm is presented that answers the question if a claw-free graph with maximum degree at most four is local-equitable \\(2\\)-colorable or not.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6616437$21339309-3C01-4552-A788-369BD9717529","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7fbfd6a9c9db4c04ae1819627a7c5da1a84e5679","datavalue":{"value":{"entity-type":"item","numeric-id":279208,"id":"Q279208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6616437$CED6A76F-9A26-4D21-BE31-332029192FFB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6616437$B07748BD-4EB1-408F-AC52-D90A4629C58E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"88b9e27231db06241e0a9f8da1cbe96156fa7be9","datavalue":{"value":"7923966","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6616437$E54D7A6E-98C1-4045-9765-317364BAEB3D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8cd1b648f97a4c4d9d30641da1cff52f719eaf16","datavalue":{"value":"local-equitable coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6616437$69A235BD-F7A8-4E10-820D-AEC7D96C5706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf2bdc388a8c2bee548ba5c2acc5f66c693118c4","datavalue":{"value":"claw-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6616437$4C516FA1-0BE0-4578-9ED5-A30E52D233B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7f1cd9bb1011b33ba44115724a57cb54f5aa1d5","datavalue":{"value":"small degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q6616437$E8C84DFF-34B1-4A55-BE31-C10A7A0A6A47","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":"Q6616437$53C3B3D7-CF2C-49F9-818D-1611D2952B08","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5b82f7b1a4073bc4c9f0009d3df8c0e8eb8773b","datavalue":{"value":{"entity-type":"item","numeric-id":4652597,"id":"Q4652597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6616437$5590446D-3E66-4A7B-B9A2-290469C5EAC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"959bd71c0950e742cd69c141c48d51cb5f1e5cd4","datavalue":{"value":{"entity-type":"item","numeric-id":3575455,"id":"Q3575455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6616437$3D45FE38-4E8B-44F5-AEC1-5ED70101AF0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4b90bbbbcae9eabe8c0ff7c9a0d842b6b3bfbbc","datavalue":{"value":{"entity-type":"item","numeric-id":3419713,"id":"Q3419713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6616437$EFA7BA13-05D9-4FCE-95DF-CEC8501476C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff78e10b473763a5802f01c541b98c94ab07e690","datavalue":{"value":{"entity-type":"item","numeric-id":4806592,"id":"Q4806592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6616437$B1FB8564-EB6B-429C-81C6-DF8F94BA89D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84f07b895a118846b0746831213426e347e89e24","datavalue":{"value":{"entity-type":"item","numeric-id":2077396,"id":"Q2077396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6616437$3EDAF2FD-5B15-4BAD-90AF-E53D6F2C81B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8517fd9ac60392d2aa9325bf76cbbfcc372e6da","datavalue":{"value":{"entity-type":"item","numeric-id":2110276,"id":"Q2110276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6616437$C6432113-FF11-497D-8D0B-28E5B292DFE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4095597a7bfb503206b269431de3cf745a4169ef","datavalue":{"value":{"entity-type":"item","numeric-id":2657098,"id":"Q2657098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6616437$D10C8269-0EEE-4739-88EF-2061F32E82B4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a8caddd8e11d789207b4809c4099a63a06bb246","datavalue":{"value":"10.1007/S00373-024-02826-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6616437$C6E31B14-2AD8-434D-95EA-8A7DDC5F944A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"509bc513c5dd480b4a2e31222e32b5336ff645b9","datavalue":{"value":{"entity-type":"item","numeric-id":2077396,"id":"Q2077396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02a5b1570d391adda2851448bde1f7b439731e5e","datavalue":{"value":{"amount":"+0.8971443772315979","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":"Q6616437$80EF8F51-A14A-4F3E-9ADA-ECFF8A89B6E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c192ff608df06d6c4c8106ec045b616f1a417dcf","datavalue":{"value":{"entity-type":"item","numeric-id":2657098,"id":"Q2657098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d605426e43ad16f60dfd9b493e8e5dac667ac62","datavalue":{"value":{"amount":"+0.881986141204834","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":"Q6616437$50A922C9-9AEF-4CFB-BE52-44670E623109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0675547c3647df47d399b3bd2813d9773eebe1ae","datavalue":{"value":{"entity-type":"item","numeric-id":2110276,"id":"Q2110276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"073c39e1b676eeb0cbf4e7c814e236fdeacc2a93","datavalue":{"value":{"amount":"+0.8120805621147156","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":"Q6616437$858344E7-B88D-420E-AA81-8A4D762F72AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ace03d11738a2e7548614cff73cfbd7a165f531e","datavalue":{"value":{"entity-type":"item","numeric-id":2631088,"id":"Q2631088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c1e5970f9eed6175caeebb04634e630392507de","datavalue":{"value":{"amount":"+0.7737147212028503","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":"Q6616437$09D01ACF-B773-4C5D-B866-8DAAD5B7795D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64b83c964e67020a327e75e66a2f0cb8479726bf","datavalue":{"value":{"entity-type":"item","numeric-id":5755526,"id":"Q5755526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa83103a116f2c1e4904b4d192efd3a619f692ec","datavalue":{"value":{"amount":"+0.7725871801376343","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":"Q6616437$12E7A50F-8686-4D84-8E75-90B95FE6A964","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of local-equitable coloring in claw-free graphs with small degree","badges":[]}}}}}