Conflict-free connection of trees

DOI10.1007/S10878-018-0363-XMaRDI QIDQ2051900zbMATHOpenAlexFDO

Authors Hong Chang, Meng Ji, Jingshu Zhang, Xueliang Li

Publication date 25 November 2021

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

treeconflict-free coloringedge ranking\(cfc\)-criticalconflict-free connection coloring

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Structural characterization of families of graphs (05C75)

Abstract: We study the conflict-free connection coloring of trees, which is also the conflict-free coloring of the so-called edge-path hypergraphs of trees. We first prove that for a tree $T$ of order $n$, $cfc(T)geqcfc(P_n)=lceillo{g}_{2}nceil$, which completely confirms the conjecture of Li and Wu. We then present a sharp upper bound for the conflict-free connection number of trees by a simple algorithm. Furthermore, we show that the conflict-free connection number of the binomial tree with $2^{k-1}$ vertices is $k-1$. At last, we study trees which are $cfc$-critical, and prove that if a tree $T$ is $cfc$-critical, then the conflict-free connection coloring of $T$ is equivalent to the edge ranking of $T$.

Recommendations

• On conflict-free connection of graphs
• Conflict-free connections of graphs
• Conflict-free connection number and independence number of a graph
• Conflict-free (vertex-)connection numbers of graphs with small diameters
• Conflict-free connection number and size of graphs

Cites work

• scientific article; zbMATH DE number 2209737 (Why is no real title available?)
• Conflict-Free Colorings of Rectangles Ranges
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-free coloring and its applications
• Conflict-free coloring of points and simple regions in the plane
• Conflict-free colourings of graphs and hypergraphs
• Conflict-free connection numbers of line graphs
• Conflict-free connections of graphs
• Deterministic conflict-free coloring for intervals: from offline to online
• Edge ranking of graphs is hard
• Graph theory
• Graph unique-maximum and conflict-free colorings
• Maximum value of conflict-free vertex-connection number of graphs
• On an edge ranking problem of trees and graphs
• On conflict-free connection of graphs
• Online Conflict‐Free Coloring for Intervals
• Optimal edge ranking of trees in linear time
• Optimal edge ranking of trees in polynomial time
• Parity vertex colorings of binomial trees
• Parity vertex colouring of graphs
• Properly colored connectivity of graphs
• Rankings of Graphs
• Unique-maximum and conflict-free coloring for hypergraphs and tree graphs

Cited in

(11)

• Interdicting facilities in tree networks
• Conflict-free vertex-connections of graphs
• Strong conflict-free connection of graphs
• Conflict-free connection number of graphs with four bridges
• Conflict-free (vertex-)connection numbers of graphs with small diameters
• A survey on conflict-free connection coloring of graphs
• scientific article; zbMATH DE number 1990721 (Why is no real title available?)
• Some results on strong conflict-free connection number of graphs
• Construction of the developing connecting tree
• Conflict-free connection number and independence number of a graph
• scientific article; zbMATH DE number 3861202 (Why is no real title available?)

This page was built for publication: Conflict-free connection of trees

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