{"entities":{"Q426778":{"pageid":428545,"ns":120,"title":"Item:Q426778","lastrevid":61758699,"modified":"2026-04-11T01:27:56Z","type":"item","id":"Q426778","labels":{"en":{"language":"en","value":"Rainbow connection number and connectivity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6045644"}},"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":"Q426778$089FCC18-9E13-4CF3-A511-BB58F948AA19","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"92556ad78cd6d6d52b8e41b047dc345dc805e6ab","datavalue":{"value":{"text":"Rainbow connection number and connectivity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q426778$8BA892B3-C205-49A4-A0FE-2C287DEA04AD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8dad67450538126509b64883570c45fed2d93408","datavalue":{"value":"1243.05133","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426778$BC4908BA-AA73-4E9A-9AD1-E1C57C1E58AC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"40746697aeae8204a8711fa863d0decbb651ca60","datavalue":{"value":{"entity-type":"item","numeric-id":400499,"id":"Q400499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426778$A2AEFB7A-4135-4400-BE9C-4F7AC642FECA","rank":"normal"},{"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":"Q426778$38F67C72-4FDF-4604-B883-2CC9F91CE655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f39a90f713dbdf70d5bc8b33df7f3270a8d73566","datavalue":{"value":{"entity-type":"item","numeric-id":300472,"id":"Q300472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426778$6195B1D3-1FEC-4CBA-9782-AE120239BCEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"58e242255041fcc36cc5d243c0bca45de04a62e9","datavalue":{"value":{"entity-type":"item","numeric-id":300473,"id":"Q300473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426778$518F82A9-A0A2-4C90-BF73-6394A8774295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2bf6b57361b3180efb360b271887d95e01377385","datavalue":{"value":{"entity-type":"item","numeric-id":831023,"id":"Q831023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426778$4640D791-E034-4D6E-B903-95E08DB972DA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426778$10500CF2-B495-44C1-B340-F8D5904E3718","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4bc8e8f32e3771ea3dc331f4cf4795267b160813","datavalue":{"value":{"time":"+2012-06-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q426778$21122444-6600-47AA-865B-20B3FE57D2C3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"426fa123520daa749f510135e59ac4649be99c6b","datavalue":{"value":"https://arxiv.org/abs/1105.5704","type":"string"},"datatype":"url"},"type":"statement","id":"Q426778$F538DDA6-C76D-40B9-91EE-16CCECDC7F1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"53bf76576ad1143dfca8b4943e325ae26187ca87","datavalue":{"value":"http://www.emis.de/journals/EJC/ojs/index.php/eljc/article/view/v19i1p20","type":"string"},"datatype":"url"},"type":"statement","id":"Q426778$7A85D3C8-49A5-4DAC-AAD7-DFD93DCAA5E8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"65976fcfad75295b83698426ad399d19fd7d2617","datavalue":{"value":"Summary: The rainbow connection number, \\(rc(G)\\), of a connected graph \\(G\\) is the minimum number of colors needed to color its edges, so that every pair of vertices is connected by at least one path in which no two edges are colored the same. Our main result is that \\(rc(G)\\leq \\lceil\\frac{n}{2}\\rceil\\) for any 2-connected graph with at least three vertices. We conjecture that \\(rc(G)\\leq n/\\kappa+C\\) for a \\(\\kappa\\)-connected graph \\(G\\) of order \\(n\\), where \\(C\\) is a constant, and prove the conjecture for certain classes of graphs. We also prove that \\(rc(G)\\leq(2+\\varepsilon)n/\\kappa+23/\\varepsilon^2\\) for any \\(\\varepsilon>0\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q426778$2C4E9DEB-045D-4DBB-A927-9266D58AF289","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426778$EE7D97AD-CBDC-4E6D-BF26-BAB3B7447041","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426778$382B7DF3-C34F-48FA-B3FD-06127E8FBB17","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c89e92bdd7193a53fe52eb5020fdb836d0249d3e","datavalue":{"value":"6045644","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426778$680487DA-3D82-4112-8BEF-DCC49A1CD017","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e026b93af489645ae783281f62a165a1d234a264","datavalue":{"value":"rainbow coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q426778$F82528FC-0977-455F-802D-B7B4F81B28EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8730e361915568d9ef68f991aa6657b31802e5be","datavalue":{"value":"rainbow connection number","type":"string"},"datatype":"string"},"type":"statement","id":"Q426778$2A634F16-68CA-44C2-8138-1AAE6688520E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q426778$95555643-27C9-4D7C-8041-52ED5F60B124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"595aaadd38382c4d651e1ace9467343ba9bd14ed","datavalue":{"value":"2-connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q426778$11B52505-27D9-4BA6-9F73-DA9A799B6F80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b52e59e3b5eb514bbd13ca76e5694c81bccaf502","datavalue":{"value":"ear decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q426778$C410C94F-63B1-400A-9DC6-408348E5432D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae41303426e6695786e3a6d28699919bfeab34a","datavalue":{"value":"chordal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q426778$C9C0B0A9-2AFF-4CD2-B151-07F19C3CFC9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q426778$99ACFA14-FD5F-42FB-A474-720714475B2F","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":"Q426778$9AC98CC5-FCA9-4E23-BE8C-16C9DE74459E","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"5a45184de61e0bf1ba03b3a9a430e17c0212ec5d","datavalue":{"value":"bafkreifqfq6lqxgorrwqnvy5ahwvtbdhnpjqa2wlppqphi5zzrioruvoqy","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426778$14CEF74E-4C6B-459A-A4A8-B757E2C9570A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b9b3fadd20c699c49dad247b907a0f554b194e7","datavalue":{"value":{"entity-type":"item","numeric-id":367069,"id":"Q367069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"659dc14cb2d9dc788958d573f79151463c735fb9","datavalue":{"value":{"amount":"+0.9164255261421204","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":"Q426778$E1B5DCB5-FEFA-4A95-985F-5FE0B758AD56","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":"36f03956782bced334f72345e0761290feb31ccf","datavalue":{"value":{"amount":"+0.913241446018219","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":"Q426778$DDCC2440-0A6B-41D0-9BD6-F9042E373F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45bdb6a851bb5e67a5ecf0beef06c0b443dba203","datavalue":{"value":{"entity-type":"item","numeric-id":1010776,"id":"Q1010776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dae002ef2b726c99962efb504818cca447d1d940","datavalue":{"value":{"amount":"+0.9084306955337524","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":"Q426778$A1EE7EEA-A223-4FB9-B177-5230B179AF8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c580c070629bb0ea563cd8cc9eb29e404acc6f4e","datavalue":{"value":{"entity-type":"item","numeric-id":2857035,"id":"Q2857035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28fb3f914511e2caa5864fe0abe0ecfa329f906f","datavalue":{"value":{"amount":"+0.9019842743873596","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":"Q426778$C0749CED-D877-4DD2-99B1-2C3BDFFFD66E","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":"80e1ca7e2e9edcf1129a6b8b340f6b31c582314c","datavalue":{"value":{"amount":"+0.901983082294464","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":"Q426778$E32DE0AC-98B3-4CF1-856C-A1C88D0E64D9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Rainbow connection number and connectivity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Rainbow_connection_number_and_connectivity"}}}}}