From Colourful to Rainbow Paths in Graphs: Colouring the Vertices
| Autor: | Stanislav Jendrol, Ingo Schiermeyer, Christoph Brause |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
0211 other engineering and technologies
021107 urban & regional planning Graph theory Rainbow 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Theoretical Computer Science Connection (mathematics) Combinatorics Integer 010201 computation theory & mathematics Path (graph theory) Discrete Mathematics and Combinatorics Pairwise comparison Connection number Mathematics |
| Zdroj: | Graphs and Combinatorics. 37:1823-1839 |
| ISSN: | 1435-5914 0911-0119 |
| DOI: | 10.1007/s00373-021-02322-9 |
| Popis: | Colourful connection concepts in graph theory such as rainbow connection, proper connection, odd connection or conflict-free connection have received a lot of attention. For an integer $$k \ge 1$$ we call a path P in a graph G k-colourful, if at least k vertices of P are pairwise differently coloured. A graph G is k-colourful connected, if any two vertices of G are connected by a k-colouful path. Now we call the least integer k, which makes G k-colourful connected, the k-colourful connection number of G. In this paper, we introduce the (strong, internal) k-colourful connection number of a graph, establish bounds for our new invariants in several graph classes as well as compute exact values for $$k\in [3]$$ . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|