2018/05/18 by Meng Ji, Xueliang Li, Ji, Meng +3
Computer Science · Mathematics · #05C15 #05C40 #68Q17 #68Q25 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1805.08072
openalex publication_date 2018/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A path in an(a) edge(vertex)-colored graph is called a conflict-free path if there exists a color used on only one of its edges(vertices). An(A) edge(vertex)-colored graph is called conflict-free (vertex-)connected if there is a conflict-free path between each pair of distinct vertices. We call the graph G strongly conflict-free connected if there exists a conflict-free path of length dG(u,v) for every two vertices u,v∈ V(G). And the strong conflict-free connection number of a connected graph G, denoted by scfc(G), is defined as the smallest number of colors that are required to make G strongly conflict-free connected. In this paper, we first investigate the question: Given a connected graph G and a coloring c: E(or V)→ \1,2,⋯,k\ (k≥ 1) of the graph, determine whether or not G is, respectively, conflict-free connected, vertex-conflict-free connected, strongly conflict-free connected under coloring c. We solve this question by providing polynomial-time algorithms. We then show that it is NP-complete to decide whether there is a k-edge-coloring (k≥ 2) of G such that all pairs (u,v)∈ P (P⊂ V× V) are strongly conflict-free connected. Finally, we prove that the problem of deciding whether scfc(G)≤ k (k≥ 2) for a given graph G is NP-complete.