{"entities":{"Q685308":{"pageid":687157,"ns":120,"title":"Item:Q685308","lastrevid":63457440,"modified":"2026-04-11T13:17:22Z","type":"item","id":"Q685308","labels":{"en":{"language":"en","value":"A note on the \\(m\\)-bounded chromatic number of a tree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417230"}},"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":"Q685308$36D5B1BC-2CEF-40B1-9BB8-A34B70D2FE9C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"02504588a9dbb8fdcbce17568717980a3cc9f11b","datavalue":{"value":{"text":"A note on the \\(m\\)-bounded chromatic number of a tree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685308$70B6A067-B5E0-437E-9C00-5812A1DA9245","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"35cabf1c1be95ed8c6a2ce879949503da1dd94b9","datavalue":{"value":"0781.05019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685308$EBD6B4CE-577D-419B-B473-B37C4D54AFE2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1104e1ddf2f1dcca8bd3af2c179ff8fc206af81","datavalue":{"value":{"entity-type":"item","numeric-id":396870,"id":"Q396870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685308$65DF0038-D163-4182-90DE-EA21D0865C92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b16ac91b3719af726a514a0e792e1b6a5d81f1db","datavalue":{"value":{"entity-type":"item","numeric-id":186290,"id":"Q186290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685308$A267B433-C11E-4D3F-853A-096D160CA362","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685308$76F06A16-57CC-4D99-976B-2D0DC23F422E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ea9458ce3029a7f683c04e43e886fdc910ea299c","datavalue":{"value":{"time":"+1993-10-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685308$52BC5733-4C5A-4CB7-9570-47E068474BE3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ddba7451afb8946c39f93cea4d85c1a543445553","datavalue":{"value":"The \\(m\\)-bounded chromatic number of a graph \\(G\\) is the smallest number of colors required for a proper coloring of \\(G\\) in which each color is used at most \\(m\\) times and is denoted by \\(\\chi_ m(G)\\). In this paper a tree \\(T\\), that is a bipartite graph, is expressed as \\(T(X,Y)\\), with the two parts \\(X\\) and \\(Y\\) explicitly written out; further, \\(\\alpha(G)\\) denotes the independence number of \\(G\\) and \\(N(v)\\) consists of all vertices adjacent to \\(v\\).   The authors establish an exact formula for the \\(m\\)-bounded chromatic number of a tree, namely: if \\(T=T(X,Y)\\) is a tree and \\(v\\) is an arbitrary vertex of maximum degree, then   (i) \\(\\chi_ m(T)=2\\) when \\(m \\geq \\max(| X |, | Y |)\\);   (ii) \\(\\chi_ m(T)=\\max(3,\\lceil| V(T)|/m \\rceil,\\lceil(| V(T)|-\\alpha (T-N(v)))/m \\rceil+1)\\) otherwise.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685308$3543DF31-E9C8-4D60-BA50-9B20549AE647","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685308$A1296099-0087-4491-81A7-DCCD674C365E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685308$EA00EA06-4745-4D7A-8E52-8FC9C7D3637D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685308$3D021C3D-E970-4C3C-90CF-2247D03AFD0A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b1de436a9eee81dca1b1c0a589110d1c6cac690e","datavalue":{"value":"417230","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685308$C40AC786-89A1-49A3-8E3E-B1ACCF585C9F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64ee277f9c936e2a123e0f0d5437796550c1db2c","datavalue":{"value":"\\(m\\)-bounded chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q685308$9E008B8F-D210-4BF1-9A24-B85450AC6086","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q685308$3B354F31-E16C-4EF9-8697-4486B98D998F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea6c2a454c967499acc6d5e80ba39aa769fd1e53","datavalue":{"value":"color","type":"string"},"datatype":"string"},"type":"statement","id":"Q685308$83AC41C0-B26D-4E96-A062-9BBE099AD1FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q685308$80A99260-E6B4-49AB-A87C-BF706B47EEDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b89aa1b9eed71217ebf6a719487a219071558409","datavalue":{"value":"independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q685308$C67152DE-F164-46E2-B2BC-1D277D529EE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13196c9c8a3f396e97e9426bc7763f437026aa4b","datavalue":{"value":"maximum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q685308$1D9BF580-0C59-4DB3-842E-F392CD7F7A87","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":"Q685308$983C2D9B-C9CF-41BF-8088-C766EAB7334B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f2fb78dae3cb9348b358c25d2a2aec96d73f2890","datavalue":{"value":"https://doi.org/10.1006/eujc.1993.1034","type":"string"},"datatype":"url"},"type":"statement","id":"Q685308$D79A6123-F46F-4398-B1EA-3215C7CE9D6F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0b1de35e2379ab267692ef28fb49c08ac2d6cae5","datavalue":{"value":"W2062597384","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685308$7A955BC2-AD8B-4AE2-963A-50672EE67666","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a467cecdddc203c7f29a1fe47b45a5fce6700398","datavalue":{"value":"10.1006/EUJC.1993.1034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685308$3E6FB441-D63D-4B93-B267-62F2299C7802","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f51e12aeb85269e831a8c2b2a29a24dcec5d580","datavalue":{"value":{"entity-type":"item","numeric-id":5937457,"id":"Q5937457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61dd97d24ae384d733aa90594b917cb0e8c9481c","datavalue":{"value":{"amount":"+0.8450616598129272","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":"Q685308$ED5707B2-CA19-4D8C-9A6A-7B372263B397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a98ee6b5a94194f7f311308db7b64d8c4ff0e8b","datavalue":{"value":{"entity-type":"item","numeric-id":686481,"id":"Q686481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a11edd191f1019855982320e86c47c1c3cf49b79","datavalue":{"value":{"amount":"+0.772470235824585","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":"Q685308$D6EA85F1-6F0D-488A-85C6-4C2807DF47EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc5b6ee8dafdcfcb80dc0bd79c0aace95db9d2e6","datavalue":{"value":{"entity-type":"item","numeric-id":512863,"id":"Q512863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eab21975bd5c8b7a574818a063015c3eee3487d9","datavalue":{"value":{"amount":"+0.7681683301925659","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":"Q685308$FE0AFF3B-AA0E-4702-9570-10C0B5C73ED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7767847a015960f73d096f9c47613d2128fecde4","datavalue":{"value":{"entity-type":"item","numeric-id":2840549,"id":"Q2840549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c3529b49bf9d1c4f960aa5d86949eec5a33bd66","datavalue":{"value":{"amount":"+0.7661826610565186","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":"Q685308$8681E557-D477-4DB2-8E8C-A4861839F2DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fa425e5833f91f73eaa0a5813515b195fdd2105","datavalue":{"value":{"entity-type":"item","numeric-id":4437297,"id":"Q4437297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6033fd7d8b99796bfbf1264a771d8c6cfa248b44","datavalue":{"value":{"amount":"+0.7654803395271301","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":"Q685308$10E5968E-13BA-4311-86C4-36C893190B5C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on the \\(m\\)-bounded chromatic number of a tree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_the_%5C(m%5C)-bounded_chromatic_number_of_a_tree"}}}}}