(Strong) conflict-free connectivity: algorithm and complexity

DOI10.1016/J.TCS.2019.10.043MaRDI QIDQ2283032zbMATH OpenOpenAlexWikidataFDO

Authors Meng Ji, Xiaoyu Zhu, Xueliang Li

Publication date 27 December 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.08072

zbMATH Keywords

complexityconflict-free connectionpolynomial-time algorithmstrong conflict-free connection

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: A path in an(a) edge(vertex)-colored graph is called emph{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 emph{conflict-free (vertex-)connected} if there is a conflict-free path between each pair of distinct vertices. We call the graph $G$ emph{strongly conflict-free connected }if there exists a conflict-free path of length $d_G(u,v)$ for every two vertices $u,vinV(G)$. And the emph{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(orV)ightarrow1,2,cdots,k(kgeq1)$ 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 $(kgeq2)$ of $G$ such that all pairs $(u,v)inP(PsubsetVimesV)$ are strongly conflict-free connected. Finally, we prove that the problem of deciding whether $scfc(G)leqk$ $(kgeq2)$ for a given graph $G$ is NP-complete.

Recommendations

• Some results on strong conflict-free connection number of graphs
• Strong conflict-free connection of graphs
• Conflict-free connections of graphs
• Conflict-free vertex-connections of graphs
• Erdős-Gallai-type results for conflict-free connection of graphs.

Cites work

• Colorful monochromatic connectivity
• Conflict-free coloring and its applications
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-free connection numbers of line graphs
• Conflict-free connections of graphs
• Conflict-free vertex-connections of graphs
• Edge ranking of graphs is hard
• Graph theory
• Graphs with conflict-free connection number two
• Hardness and algorithms for rainbow connection
• Local optimization on graphs
• Maximum value of conflict-free vertex-connection number of graphs
• On conflict-free connection of graphs
• On proper-path colorings in graphs
• Ordered colourings
• Proper connection of graphs
• Properly colored connectivity of graphs
• Rainbow connection in graphs
• Rankings of Graphs

Cited in

(11)

• Conflict-free connections of graphs
• On the \(k\)-component independence number of a tree
• Conflict-free connection number of random graphs
• Hardness results for three kinds of colored connections of graphs
• Strong conflict-free connection of graphs
• scientific article; zbMATH DE number 4119945 (Why is no real title available?)
• Some results on strong conflict-free connection number of graphs
• Conflict-free (vertex-)connection numbers of graphs with small diameters
• A survey on conflict-free connection coloring of graphs
• The parameterized complexity of strong conflict-free vertex-connection colorability
• The complexity of strong conflict-free vertex-connection k-colorability

This page was built for publication: (Strong) conflict-free connectivity: algorithm and complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2283032)