From Colourful to Rainbow Paths in Graphs: Colouring the Vertices

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 ≥ 1 we call a path P in a graph G k -colourful, if at least k vertices of P are pairwise differently coloured. A...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2021-09, Vol.37 (5), p.1823-1839
Main Authors: Brause, Christoph, Jendrol’, Stanislav, Schiermeyer, Ingo
Format: Article
Language:English
Subjects:
Apexes
Coloring
Combinatorics
Engineering Design
Graph theory
Integers
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ≥ 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 ∈ [ 3 ] .
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-021-02322-9