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

DOI10.1142/S1793830918500593MaRDI QIDQ4554541zbMATH OpenOpenAlexWikidataFDO

Authors Zhenzhen Li, Baoyindureng Wu

Publication date 14 November 2018

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

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

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)

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..

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.

Cites work

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