{"entities":{"Q1894778":{"pageid":1905520,"ns":120,"title":"Item:Q1894778","lastrevid":73717455,"modified":"2026-04-14T17:01:29Z","type":"item","id":"Q1894778","labels":{"en":{"language":"en","value":"The irregular coloring number of a tree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 778542"}},"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":"Q1894778$4B542348-29A0-40C6-92DA-1F99A5A80D98","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2ed184f11c63920c7d2f8f3f5ebeb4d8d88d48c2","datavalue":{"value":{"text":"The irregular coloring number of a tree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1894778$2CC50FEB-2F1B-4D5E-A02B-4A5C7F3F8C73","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1029f7149c3be5fed8ed679553be77231750cdb3","datavalue":{"value":"0829.05027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894778$F9649320-CA81-4BBD-881C-2538EF572222","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"69e5502c2f48459b0bbf9dc23c0b7071c0abc971","datavalue":{"value":"10.1016/0012-365X(93)E0225-S","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894778$D3715B8E-CE58-416C-B2EC-D127D2B7979C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c96c7f6ce27a69a4cbd911505470827e99d9daeb","datavalue":{"value":{"entity-type":"item","numeric-id":1894777,"id":"Q1894777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894778$981EB37E-0E9A-44EF-B19A-85FA56DA866A","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":"Q1894778$6E4AA6C1-B29F-4179-BC88-5217B98EED03","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"760e4532129a46aa27cf7d362e2e1fc1f1b35c28","datavalue":{"value":{"time":"+1996-01-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1894778$4D07BEB2-1463-4DCA-9F51-3BB8E4AF9009","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b3d629971534faf56893bb6a954a7bd88674b48d","datavalue":{"value":"An edge-coloring of a graph \\(G = (V,E)\\) is vertex-distinguishing, if for every edge \\((v,w) \\in E\\), the multiset of colors assigned to edges incident to \\(v\\) differs from the multiset of colors assigned to edges incident to \\(w\\). The minimum number of colors of a vertex-distinguishing edge-coloring of \\(G\\) is the irregular coloring number of \\(G\\), denoted by \\(c(G)\\). If \\(n_i(G)\\) denotes the number of vertices in \\(G\\) of degree \\(i\\), then an easy argument shows that \\(c(G) \\geq \\max \\bigl(n_1(G), \\sqrt {2n_2 (G)}- {1\\over 2}\\bigr)\\). The main result of this paper is a proof, that for every tree \\(T\\) with at least three vertices, \\(c(T) \\leq \\max \\bigl(n_1(T), 4.62 \\sqrt {n_2 (T)}, 8\\bigr) + 1\\). The proof is constructive, and provides an algorithm that produces the required vertex-distinguishing coloring.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894778$067387DB-4BDB-427F-9E62-CDA245E6AC6D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894778$E834B6FF-5ED9-414F-8B31-9EC04ED0CC83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894778$7F734A29-6AF8-4960-9E1A-1DE4ADDB11EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894778$98E253C2-A4AA-46B9-B5B5-2CE5CE961A46","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8dca9d5c7448b065bca14c7c71c7de57b844fe79","datavalue":{"value":"778542","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894778$4E27FE90-97ED-41A6-A73B-E5E959FB474A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5460c444abb9d7604f90c4e16cd9cc2ad2a35457","datavalue":{"value":"edge-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894778$AD69789C-9B1C-45B2-A4F1-B8A257FE5BD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15dbe2227148cc0efd25b26e7a8a7a28dc8ab863","datavalue":{"value":"irregular coloring number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894778$A41AE802-DE31-4435-B89B-54C363913A1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894778$B0F892FE-034D-4FCC-9C76-8DB4879E9787","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":"Q1894778$CC16B980-2996-480A-A44A-8D1A8F2F9BF0","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":"Q1894778$3086C99F-0A9B-463A-B544-61F4FD3C0F68","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"87e526e77d3b54cb7f01f30178c69c66b84084b5","datavalue":{"value":{"entity-type":"item","numeric-id":3971995,"id":"Q3971995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894778$A43CC757-6656-4CAA-B08B-6093E94EF5EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18623eceffdab15fc63885b511530ac13ea8fd06","datavalue":{"value":{"entity-type":"item","numeric-id":4028414,"id":"Q4028414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894778$AADB3A44-E790-4BA0-B122-81ABC940F7C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"528c3cc73477eab5cc1a074aee0afb5070b5b757","datavalue":{"value":{"entity-type":"item","numeric-id":4028274,"id":"Q4028274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894778$B2C0BB25-5E87-45C7-BF88-B33EF114B8E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c077f2d5cd16af725f9d305facd139f2ff73cb4b","datavalue":{"value":{"entity-type":"item","numeric-id":3824455,"id":"Q3824455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894778$414A5F6B-A7D1-457F-AC74-ED76CF435862","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c31bbc6bafa2e624d72b3af58fd68e767e411435","datavalue":{"value":{"entity-type":"item","numeric-id":4873753,"id":"Q4873753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894778$11177F6D-7387-4BAA-9B90-DBF87FF7CF09","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"848c6d77eb0e539760324405e2bc8f4147afee32","datavalue":{"value":{"entity-type":"item","numeric-id":4863418,"id":"Q4863418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04386de106a85650c6b03232373516e605ecb683","datavalue":{"value":{"amount":"+0.8467985391616821","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":"Q1894778$C4ECEC52-2204-4CE5-A811-A61B5B87E2E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"392bf386f29f429e1900b70491d4f5b469d18929","datavalue":{"value":{"entity-type":"item","numeric-id":3385750,"id":"Q3385750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9fc205b4a363a1202a0e489bd3aeaec06869e17","datavalue":{"value":{"amount":"+0.8462960720062256","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":"Q1894778$5EF16B91-F790-4E80-AC07-205504AB8D5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be0abab9dfcf7e0e983f2ef555ec51d29891c1c0","datavalue":{"value":{"entity-type":"item","numeric-id":4028414,"id":"Q4028414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"966ebc3061478f9a715520a49db746dd63d422ee","datavalue":{"value":{"amount":"+0.835148274898529","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":"Q1894778$98EEF038-C952-4367-9485-2DC16554079F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec011058964c6dee20a09c4e50d83eb12a71e7ea","datavalue":{"value":{"entity-type":"item","numeric-id":3429529,"id":"Q3429529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bee8e08b0e8df578b95e9c751701ce7fa46a978","datavalue":{"value":{"amount":"+0.8311382532119751","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":"Q1894778$575932B0-79EA-4092-96DF-00D6A85A2AE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e51c5884233c6b610b2e9114b270bf2a92b390a8","datavalue":{"value":{"entity-type":"item","numeric-id":4362092,"id":"Q4362092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3430ffb5c2050ddd79be58cb12183b8acd1597ca","datavalue":{"value":{"amount":"+0.8279753923416138","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":"Q1894778$5D325F02-4F76-4062-9788-BC926AEDB58B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The irregular coloring number of a tree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_irregular_coloring_number_of_a_tree"}}}}}