{"entities":{"Q1283791":{"pageid":1294541,"ns":120,"title":"Item:Q1283791","lastrevid":70575642,"modified":"2026-04-13T15:33:16Z","type":"item","id":"Q1283791","labels":{"en":{"language":"en","value":"The b-chromatic number of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1271069"}},"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":"Q1283791$F1BFF2D5-8D06-45B8-9FE6-5310A8AC86D4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"22d7e018ce1a7703b26e34eb134f54c400953e82","datavalue":{"value":{"text":"The b-chromatic number of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1283791$E6489E1D-BA32-40A8-ADA1-F7E5E852CE94","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5fcc210f51493edc407e54a62ee14bc7eeeae27b","datavalue":{"value":"0933.05051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283791$4B1F5004-2180-4EE3-AEF0-6C155AB49957","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"275deb761ca64304aac3023240420e3b67ecc606","datavalue":{"value":"10.1016/S0166-218X(98)00146-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283791$D99408BC-8690-498B-9CDD-D16DD4A09E6A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9380ba3d7192d4700d42b0d094e27aae962de032","datavalue":{"value":{"entity-type":"item","numeric-id":314432,"id":"Q314432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$2558040F-00D4-42D6-9857-9ABB3854B7D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"61f517b2ca6f430e1715cd44a60181220140b79f","datavalue":{"value":{"entity-type":"item","numeric-id":301928,"id":"Q301928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$18CB2420-12F6-49A6-AA64-658493220DE7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$9AA426FC-2F29-4BC9-B538-AF14A39F7742","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"979b9c92840250b4df3da98e1edcce8b5f7b9bab","datavalue":{"value":{"time":"+1999-12-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1283791$BEFFC138-C92F-4ED5-AB24-3C5F305CB217","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4e305a4d9006e2bc0f2dfe852313272efe677df7","datavalue":{"value":"The achromatic number of a graph \\(G= (V,E)\\) is the maximum \\(k\\) such that \\(V\\) can be partitioned into \\(k\\) independent sets with no union of a pair of these sets again independent. The authors show that this can be expressed using a partial order on the set of partitions of \\(V\\). A partition is said to be smaller than another partition if it can be obtained from the latter by replacing two sets by their union, or by a transitive closure of this relation. Then the achromatic number is the maximum size of a minimal element under this partial order of the partitions of \\(V\\) into independent sets. If we take another partial order, using instead of taking the union, the distribution of elements of one set over the other sets, then the parameter obtained is the newly introduced b-chromatic number of the graph. Alternatively, the b-chromatic number of a graph \\(G= (V,E)\\) an be defined as the maximum \\(k\\), such that \\(V\\) can be partitioned into \\(k\\) independent sets such that each independent set contains at least one vertex that is adjacent to each other independent set. The b-chromatic number problem is shown to be NP-complete. Also, the authors show that the problem can be solved exactly for trees, giving a precise characterization of the b-chromatic number. This characterization is in terms of the degrees of the vertices and adjacencies of vertices with vertices of certain degrees, and can easily be checked in linear time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283791$FB98F5FA-0FD0-4D0E-9FD7-6D0630326AB8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283791$DDDFF0AF-0374-4CBB-8291-FAFE69CC850C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283791$6692CBBE-BB14-4025-B00F-95E43121D363","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283791$4BAB1678-F2C4-47C1-A8E2-DBA131DBC8A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283791$AB4C1065-2EEE-41D8-89E3-4C716D56AC68","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"05d1c9e2166d59c9875fcccd91b7c640b956f1a8","datavalue":{"value":"1271069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283791$F022E8DB-3A00-4A0F-B2B0-5BBCAE95B54D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd81b2942e8899c2ccc907b7e9232a24db5f5ce3","datavalue":{"value":"achromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283791$F13F920E-213A-4BC5-816C-06CBDF123D59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9890d2d31de82fcf86b74b799289b36efeaabea2","datavalue":{"value":"independent sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283791$1569C648-ED31-469C-B1AA-091D8FCB3DF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e41fb471c5632503b8716f23269ac7a1a49e160e","datavalue":{"value":"partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283791$97DE1C2D-0DE0-4754-A4FE-BDDD32AB002D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f671311496f757970e990cf8512b7e8c8ece28f5","datavalue":{"value":"b-chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283791$D8E9D38D-BE67-498E-B720-0883F221863A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283791$E5404837-09A9-4E04-A807-F70D7ADE96AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c89639778a113cbe54a2efcba7f98ccd79f62275","datavalue":{"value":"characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283791$7B02E97F-A74E-46B7-81CC-FCC3CDB18ADC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eea1ea35de576c62b8101835521aa928ecd629a1","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$6914DBFD-DFE4-4C51-9748-7BDD86810900","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":"Q1283791$76A70BA7-17BE-4396-9CDC-F0744F8F09DB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac7f04bfc755103b505310e94b46f9d83558eff1","datavalue":{"value":{"entity-type":"item","numeric-id":1825646,"id":"Q1825646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$92ED008C-5A6E-4A0A-8D1F-E911DE05C329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3628f1effd0c1124025a6bdbd498396fd56263e","datavalue":{"value":{"entity-type":"item","numeric-id":4364806,"id":"Q4364806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$4DCE3894-61BB-46A4-A96D-9DBCC7059764","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bed38fc2d8972f123567d5008027234baa9c0980","datavalue":{"value":{"entity-type":"item","numeric-id":753848,"id":"Q753848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$037BC9A6-B8BF-41F6-AC26-F6EEE49064DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24a4956304e6bb9a4c12cb7f429c7804fdc6f8de","datavalue":{"value":{"entity-type":"item","numeric-id":1136777,"id":"Q1136777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$8F6E310D-5397-4665-ABB4-3C6FFB839994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2195fcf50c30bfb3d44ec94fc1feab3ae8df026e","datavalue":{"value":{"entity-type":"item","numeric-id":1065819,"id":"Q1065819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$C812F075-2E2A-45E4-9AD1-90619D67E9BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$00B00161-88ED-4402-B088-579D2FE9C913","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c7a1b4e281fafcfccd2c74427df8f8ed44bd786","datavalue":{"value":{"entity-type":"item","numeric-id":685520,"id":"Q685520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$FC1CD43C-5AE4-4677-B386-3E87B8DAF379","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7910a682b401dcd40836466f91765986cec8a42d","datavalue":{"value":{"entity-type":"item","numeric-id":3661618,"id":"Q3661618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$AB25A3F5-9D92-40EF-A856-A74837478FF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dff1b6998120ff9e6ad67c6efd96c489b7dbac09","datavalue":{"value":{"entity-type":"item","numeric-id":5591379,"id":"Q5591379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$CB21E525-2029-4B76-9893-73D91B78DB48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4327677991eb2845cc8d90a47d7438e36ce2734","datavalue":{"value":{"entity-type":"item","numeric-id":5578801,"id":"Q5578801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$AB7B7413-F63C-4F6A-AD80-23A575C43986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2f7cee5ab9f468b6c01bc006a2b0b5d8926cdb9","datavalue":{"value":{"entity-type":"item","numeric-id":3791195,"id":"Q3791195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$51DD060A-9C4E-48E5-91A1-557E12ACD114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff164d55a743a1d0e596c39ca6f04faf5a1b7a4e","datavalue":{"value":{"entity-type":"item","numeric-id":3126442,"id":"Q3126442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$31CDE760-0170-4D38-A7FB-E25594E5F753","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2be894136bbddcd6009199eaf9e6862c68de70b3","datavalue":{"value":{"entity-type":"item","numeric-id":750159,"id":"Q750159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$E96D8CEE-F5C7-43EC-A5BC-0AEAE13EB9E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e7032db704a3c4fcea69481a5580e82a7d02eda","datavalue":{"value":{"entity-type":"item","numeric-id":3903038,"id":"Q3903038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283791$596D4D53-0743-46CD-9C1F-D2131E414620","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1bea94aecd3e8ae91594c5009a48778e270a6840","datavalue":{"value":"Q131685792","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283791$3D8A610E-E3CF-493E-9372-2277293392E4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17194dbe07a282953af9634f3ec6641fc2ff0ec9","datavalue":{"value":{"entity-type":"item","numeric-id":5363791,"id":"Q5363791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1b9be1d79be4ac20f012baaa108ede1e45d1999","datavalue":{"value":{"amount":"+0.8485905528068542","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":"Q1283791$B578FC98-D096-4984-A7D7-1839A7A9F7BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4d98a3d77a64f1658b06257fda175d3d8d8292f","datavalue":{"value":{"entity-type":"item","numeric-id":3216676,"id":"Q3216676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"514770346c9fecf92bb7d45c54722a5995335223","datavalue":{"value":{"amount":"+0.8335357308387756","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":"Q1283791$95D54BFB-0A1E-4292-98BC-73B242D9D7E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc3bafa48da6de3359f28f8d3df2bda2250fe565","datavalue":{"value":{"entity-type":"item","numeric-id":4414507,"id":"Q4414507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"793da3a7781a80d95187102481f3ba95654c0bba","datavalue":{"value":{"amount":"+0.8275896310806274","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":"Q1283791$DF66CAD5-4698-4913-9188-9C36E0F607BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a8beb52e8c1c11d6da21bd3539132107d2876fa","datavalue":{"value":{"entity-type":"item","numeric-id":340565,"id":"Q340565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad9e01f458fadfd8001d161f4b5ee1805c20d811","datavalue":{"value":{"amount":"+0.8214590549468994","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":"Q1283791$07E82A4F-C7EE-4F54-BB2E-9C28DD582BEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb16e6104c119704d28b131c3702eb6415f63ea5","datavalue":{"value":{"entity-type":"item","numeric-id":4483922,"id":"Q4483922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5129ffd07b414eb6a963e1a0a506f6117126b90","datavalue":{"value":{"amount":"+0.8117621541023254","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":"Q1283791$DD8291AC-8C4F-492D-9519-27FBE43B6A89","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The b-chromatic number of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_b-chromatic_number_of_a_graph"}}}}}