Degree sum conditions for a graph to have bounded conflict-free connection number

Abstract

A path in an edge-coloured graph is called \emph{conflict-free} if a colour is exclusively applied to one of its edges. A graph $G$ is considered \emph{conflict-free connected} if every pair of vertices in $V(G)$ is connected by a conflict-free path. The minimum number of colours required to render a connected graph $G$ conflict-free connected is referred to as the \emph{conflict-free connection number}. In this paper, we introduce several sharp conditions on the minimum degree sum of any $4$ independent vertices in $G$ to ensure that the conflict-free connection number of $G$ is bounded.

20 pages