Rainbow Connection In Sparse Graphs
An edge-coloured connected graph G = (V,E) is called rainbow-connected if each pair of distinct vertices of G is connected by a path whose edges have distinct colours. The rainbow connection number of G, denoted by rc(G), is the minimum number of colours such that G is rainbow-connected. In this pap...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2013-03-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1640 |
| _version_ | 1797713131277910016 |
|---|---|
| author | Kemnitz Arnfried Przybyło Jakub Schiermeyer Ingo Woźniak Mariusz |
| author_facet | Kemnitz Arnfried Przybyło Jakub Schiermeyer Ingo Woźniak Mariusz |
| author_sort | Kemnitz Arnfried |
| collection | DOAJ |
| description | An edge-coloured connected graph G = (V,E) is called rainbow-connected if each pair of distinct vertices of G is connected by a path whose edges have distinct colours. The rainbow connection number of G, denoted by rc(G), is the minimum number of colours such that G is rainbow-connected. In this paper we prove that rc(G) ≤ k if |V (G)| = n and for all integers n and k with n − 6 ≤ k ≤ n − 3. We also show that this bound is tight. |
| first_indexed | 2024-03-12T07:32:27Z |
| format | Article |
| id | doaj.art-2ae0a44c6dd64419bae4ab99ea9e8440 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T07:32:27Z |
| publishDate | 2013-03-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-2ae0a44c6dd64419bae4ab99ea9e84402023-09-02T21:43:05ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922013-03-0133118119210.7151/dmgt.1640Rainbow Connection In Sparse GraphsKemnitz Arnfried0Przybyło Jakub1Schiermeyer Ingo2Woźniak Mariusz3Computational Mathematics, Technische Universit¨at Braunschweig 38 023 Braunschweig, GermanyAGH University of Science and Technology al. A. Mickiewicza 30, 30-059 Krakow, PolandInstitut f¨ur Diskrete Mathematik und Algebra Technische Universit¨at Bergakademie Freiberg 09 596 Freiberg, GermanyAGH University of Science and Technology al. A. Mickiewicza 30, 30-059 Krakow, PolandAn edge-coloured connected graph G = (V,E) is called rainbow-connected if each pair of distinct vertices of G is connected by a path whose edges have distinct colours. The rainbow connection number of G, denoted by rc(G), is the minimum number of colours such that G is rainbow-connected. In this paper we prove that rc(G) ≤ k if |V (G)| = n and for all integers n and k with n − 6 ≤ k ≤ n − 3. We also show that this bound is tight.https://doi.org/10.7151/dmgt.1640rainbow-connected graphrainbow colouringrainbow connection number |
| spellingShingle | Kemnitz Arnfried Przybyło Jakub Schiermeyer Ingo Woźniak Mariusz Rainbow Connection In Sparse Graphs Discussiones Mathematicae Graph Theory rainbow-connected graph rainbow colouring rainbow connection number |
| title | Rainbow Connection In Sparse Graphs |
| title_full | Rainbow Connection In Sparse Graphs |
| title_fullStr | Rainbow Connection In Sparse Graphs |
| title_full_unstemmed | Rainbow Connection In Sparse Graphs |
| title_short | Rainbow Connection In Sparse Graphs |
| title_sort | rainbow connection in sparse graphs |
| topic | rainbow-connected graph rainbow colouring rainbow connection number |
| url | https://doi.org/10.7151/dmgt.1640 |
| work_keys_str_mv | AT kemnitzarnfried rainbowconnectioninsparsegraphs AT przybyłojakub rainbowconnectioninsparsegraphs AT schiermeyeringo rainbowconnectioninsparsegraphs AT wozniakmariusz rainbowconnectioninsparsegraphs |