Maximum value of conflict-free vertex-connection number of graphs

DOI10.1142/S1793830918500593zbMATH Open1400.05085arXiv1709.01225OpenAlexW2884611810WikidataQ129617090 ScholiaQ129617090MaRDI QIDQ4554541FDOQ4554541

Authors: Zhenzhen Li, Baoyindureng Wu 

Publication date: 14 November 2018

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Abstract: A path in a vertex-colored graph is called {it conflict-free} if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be {it conflict-free vertex-connected} if any two vertices of the graph are connected by a conflict-free path. The {it conflict-free vertex-connection number}, denoted by $vcfc(G)$, is defined as the smallest number of colors required to make $G$ conflict-free vertex-connected. Li et al. conjectured that for a connected graph $G$ of order $n$, $vcfc(G)leqvcfc(P_n)$. We confirm that the conjecture is true and pose a a relevant conjecture concerning the conflict-free connection number introduced by Czap et al..

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

Recommendations

• Conflict-free vertex-connections of graphs
• Conflict-free vertex connection number at most 3 and size of graphs
• The conflict-free vertex-connection number and degree conditions of graphs
• Conflict-free (vertex-)connection numbers of graphs with small diameters
• Erdős-Gallai-type results for conflict-free connection of graphs.

zbMATH Keywords

conflict-free connectionconflict-free vertex-connection

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40) Structural characterization of families of graphs (05C75)

Cites Work

• Graph theory
• Optimal node ranking of trees
• Ordered colourings
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-free colourings of graphs and hypergraphs
• Graph unique-maximum and conflict-free colorings
• Unique-maximum and conflict-free coloring for hypergraphs and tree graphs
• Conflict-free connections of graphs

Cited In (11)

• On the \(k\)-component independence number of a tree
• Conflict-free connection of trees
• On conflict-free connection of graphs
• Some results on strong conflict-free connection number of graphs
• Conflict-free connection number and independence number of a graph
• Conflict-free connection number and size of graphs
• Conflict-free vertex connection number at most 3 and size of graphs
• Conflict-free vertex-connections of graphs
• (Strong) conflict-free connectivity: algorithm and complexity
• A survey on conflict-free connection coloring of graphs
• The conflict-free vertex-connection number and degree conditions of graphs

This page was built for publication: Maximum value of conflict-free vertex-connection number of graphs

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