{"entities":{"Q2138952":{"pageid":2149695,"ns":120,"title":"Item:Q2138952","lastrevid":57752367,"modified":"2026-04-01T06:54:42Z","type":"item","id":"Q2138952","labels":{"en":{"language":"en","value":"Upper bounding rainbow connection number by forest number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7527676"}},"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":"Q2138952$5B3887B9-4A04-4470-9B39-4FC6F1BA9170","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"346357ba297928fb9c0459ef2be25fbbd6cab234","datavalue":{"value":{"text":"Upper bounding rainbow connection number by forest number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2138952$EC895EF3-76AA-4982-B47D-49DD72670D60","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c72bff0cfec81c47d73dd784eed3ac4c312a4749","datavalue":{"value":"1490.05067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138952$DA531A86-F0F1-4EDF-9ED4-44B00F7B48BA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"abcd67b883bdb135fa3e2d4d00b0f0c8f6d98bc4","datavalue":{"value":{"entity-type":"item","numeric-id":300471,"id":"Q300471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$49B38535-4426-453E-847E-FE3A9AF5B685","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9bc306d1b7a8f430938fffd4a92b48d1d1330584","datavalue":{"value":{"entity-type":"item","numeric-id":1633612,"id":"Q1633612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$9CCC7407-983E-4DEC-858D-6391A0CD655E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f8e6b1ad5a62039e802272074c1a30e6abb3b23","datavalue":{"value":{"entity-type":"item","numeric-id":266283,"id":"Q266283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$78A47936-377B-4539-A8F6-B230646DC937","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"10d3db4c2674a171141b0ad2d7fea6e0410b4f8e","datavalue":{"value":{"entity-type":"item","numeric-id":295636,"id":"Q295636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$887BD447-77E7-4A84-8867-DC5C74B59BA3","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":"Q2138952$C39E4F18-1FF6-416E-BEA2-264BC04C538D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a56af58cfd4d3b017f8833425a5cd2b6e7283d16","datavalue":{"value":{"time":"+2022-05-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":"Q2138952$05F01C5F-F27A-489B-B4A3-BA4C8877E703","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"186742208718922cadcf2964369455b52bae5a32","datavalue":{"value":"https://arxiv.org/abs/2006.06551","type":"string"},"datatype":"url"},"type":"statement","id":"Q2138952$03647BC1-7A64-4975-8299-094716A51080","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7294f8613ae98927273d7019f249187bd2c6a208","datavalue":{"value":"A path in a (not necessarily proper) edge-colouring of a graph is said to be rainbow if no two edges in it are the same colour, and a graph is rainbow-connected if there is a rainbow path between any two vertices of the graph. The rainbow connection number \\(\\text{rc}(G)\\) of a graph \\(G\\) is the smallest number of colours needed to produce a rainbow-connected colouring of \\(G\\).  An obvious upper bound is \\(\\text{rc}(G)\\leq \\vert V(G)\\vert -1\\) obtained by taking a spanning tree of \\(G\\) and giving each of its \\(\\vert V(G)\\vert -1\\) edges a different colour. As this bound feels quite crude, one might ask if, for example, it is possible to bound \\(\\text{rc}(G)\\) above by other parameters related to the tree and forest structure of the graph. The main result of the paper is that if we define the forest number \\(f(G)\\) of a graph to be the number of vertices in the largest induced forest in the graph, then \\(\\text{rc}(G)\\leq f(G)+2\\). This is within an additive constant 3 of best possible as trees have \\(\\text{rc}(G)=\\vert V(G)\\vert - 1=f(G)-1\\). Determination of the best result is left as an open problem.  For a little insight into the proof, the authors fix a maximum induced forest in \\(G\\) and contract each component of that forest to a single vertex. Call the resulting graph \\(H\\), it has tree vertices (from the contracted trees) and non-tree vertices. A judiciously chosen spanning tree of \\(H\\) is then chosen. The idea is now to use a small number of surplus colours to finish off the colouring after colouring the maximum forest with \\(f(G)-1\\) colours, though technical issues arise with this.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138952$5DEC5510-9E1D-4366-9A0A-AE508D3525EA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138952$B75AE373-F067-4EFD-83FE-B53C8C6E960E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138952$6DA08563-01CB-46F8-9CCA-21A538DFDB44","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4c41321df574a7a2c7c6c342448b10f930316cef","datavalue":{"value":"7527676","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138952$246174B4-6D7E-45CC-99EB-A73288C5ACF1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01cb77121550ebd4ae71bd1c67a50686b31a29a0","datavalue":{"value":"rainbow connection","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138952$C5E27E91-484E-4D91-B089-28151E7B9E59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c6bb61656a457cf1aa6111c79d913e2e1c6ab7b","datavalue":{"value":"forest number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138952$F438B2E2-D0EE-4B7B-8C2A-FBC86A9E6253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138952$AA9E45AD-5BEF-4545-82C8-A51E5B8347B7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0b0cea8603b4de1ffd54cda6d37d129691a25c2","datavalue":{"value":{"entity-type":"item","numeric-id":590772,"id":"Q590772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$386E5597-0ED1-4447-8283-4F49CB38E33D","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"b03fb07a1ad59ff4771a02807c48bbe141c78c46","datavalue":{"value":{"entity-type":"item","numeric-id":36871,"id":"Q36871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$E9704F1F-521C-4B57-BE98-94833E0F2B47","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":"Q2138952$F3E157AF-BD9C-49A8-BA9C-0A991863FB1A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b1524e3b2b78f4913740e7db28bec3f1a319e91c","datavalue":{"value":"W4214717099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138952$709C919B-3218-4553-B1EA-76DEE4D09079","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a07626c5d8ea289522f1e057da85d22f32a7485e","datavalue":{"value":{"entity-type":"item","numeric-id":742568,"id":"Q742568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$E06AC9F5-BB08-4DA1-83A7-B97A32D13069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f19efb15b356d57240fc6db5e03866456a49cb93","datavalue":{"value":{"entity-type":"item","numeric-id":1010776,"id":"Q1010776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$E82B0665-DDB5-4B5B-8BC9-526C7DECBF88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dcef6b29d2127abb61e8f2aaf9e591bfdbd0f0b","datavalue":{"value":{"entity-type":"item","numeric-id":491198,"id":"Q491198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$8D41EE28-DB75-4D9B-8809-FFE1DFF685C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89f14c27a2ea87c670a1006c7875cb9679a66258","datavalue":{"value":{"entity-type":"item","numeric-id":2911064,"id":"Q2911064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$44CC9FE6-D944-4934-9906-9185AC8610FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d00f0d21c10977bd500dd475802d6c1b1d717813","datavalue":{"value":{"entity-type":"item","numeric-id":3392716,"id":"Q3392716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$5E72D391-72AE-4BE7-B06F-F3ACD13C6881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce3971f36f4273f8a19c425b7743dd6c388342c2","datavalue":{"value":{"entity-type":"item","numeric-id":477332,"id":"Q477332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$35F9DC2C-C658-4205-B567-E80569D49ED3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34ca719bc90d53fe74062ec844755c216d321af2","datavalue":{"value":{"entity-type":"item","numeric-id":383747,"id":"Q383747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$3D079888-9248-4733-92B1-6F60001AAADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"833f7b1d3491b8a28fe6c0e6b40a73b4fecbbd5c","datavalue":{"value":{"entity-type":"item","numeric-id":5190328,"id":"Q5190328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$DAD5DB80-BABF-4626-941E-133393203EA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"945167b77c4a88034588b0a34034f17850a3bdc7","datavalue":{"value":{"entity-type":"item","numeric-id":944740,"id":"Q944740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138952$7FEA341D-33DE-4614-BD6C-F77491059CDE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f2d6b4d239911c3532e2137789cc6c76d033e0bb","datavalue":{"value":"10.1016/J.DISC.2022.112829","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138952$1F3DA244-592F-4D33-9ACA-57294339BB59","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"798a7c87db8e79bf356d83d85cf10febf55e5439","datavalue":{"value":{"entity-type":"item","numeric-id":3089362,"id":"Q3089362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c538bc11ffb740d8689521a8e8fa4cff9fcf8e4","datavalue":{"value":{"amount":"+0.8308378458023071","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":"Q2138952$645DCB21-BCFC-4A4A-ABF7-BB8D8AD0B07D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9cf8e74a3c8e917475f9f139a833beb4a5363b8","datavalue":{"value":{"entity-type":"item","numeric-id":2346333,"id":"Q2346333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cc92107e452e909a2788ad0755a20a45b7159e3","datavalue":{"value":{"amount":"+0.8231580853462219","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":"Q2138952$72A0AC42-83E0-4E1C-B14C-023971040857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"899946cadbb0ea1fc0429bc3ed91c9f559e912f6","datavalue":{"value":{"entity-type":"item","numeric-id":2446307,"id":"Q2446307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1bea146c9cb0639b29728a79c4bfda837c62e4b","datavalue":{"value":{"amount":"+0.8215793967247009","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":"Q2138952$0B675D65-E0F3-42F0-BF53-EC0A97EC16CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abbe898983c5803efb43cf7ef15677c738a8aafe","datavalue":{"value":{"entity-type":"item","numeric-id":3134374,"id":"Q3134374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63410e3b650f31bd1d5e60cf15681186feff329b","datavalue":{"value":{"amount":"+0.8193961977958679","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":"Q2138952$FE484882-37B1-4DE4-BC08-747BA19EF199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"519ac6d4ea4941ae59bc9f4363c35fdc2bc8e0c7","datavalue":{"value":{"entity-type":"item","numeric-id":383747,"id":"Q383747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1036e1dedff97cf4cf5455bc4d8887f8d7059ae9","datavalue":{"value":{"amount":"+0.8173943161964417","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":"Q2138952$6CB711D4-B8FC-4ED6-AE56-B5EB20125B1A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2138952","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2138952"}}}}}