Conflict-Free Vertex Connection Number At Most 3 and Size of Graphs

Abstract

A path in a vertex-coloured graph is called conflict-free if there is a colour used on exactly one of its vertices. A vertex-coloured graph is said to be conflict-free vertex-connected if any two distinct vertices of the graph are connected by a conflict-free vertex-path. The conflict-free vertex-connection number, denoted by vcfc(G), is the smallest number of colours needed in order to make G conflict-free vertex-connected. Clearly, vcfc(G) ≥ 2 for every connected graph on n ≥ 2 vertices.

Keywords

• vertex-colouring
• conflict-free vertex-connection number
• size of graph
• 05c15
• 05c40
• 05c07