Conflict-free connection of trees

DOI10.1007/S10878-018-0363-XzbMATH Open1479.05096arXiv1712.10010OpenAlexW2963588339MaRDI QIDQ2051900FDOQ2051900

Xueliang Li, Jingshu Zhang, Hong Chang, Meng Ji

Publication date: 25 November 2021

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

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

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

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

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)

Cites Work

• Graph theory
• Rainbow connections of graphs: a survey
• Rankings of Graphs
• On an edge ranking problem of trees and graphs
• Optimal edge ranking of trees in polynomial time
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Deterministic conflict-free coloring for intervals
• Online Conflict‐Free Coloring for Intervals
• Conflict-Free Colourings of Graphs and Hypergraphs
• Conflict-Free Coloring and its Applications
• Conflict-free coloring of points and simple regions in the plane
• Conflict-Free Colorings of Rectangles Ranges
• Title not available (Why is that?)
• Parity vertex colouring of graphs
• Graph unique-maximum and conflict-free colorings
• Edge ranking of graphs is hard
• Properly Colored Connectivity of Graphs
• Optimal edge ranking of trees in linear time
• Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs
• Conflict-free connections of graphs
• Conflict-free connection numbers of line graphs
• On conflict-free connection of graphs
• Maximum value of conflict-free vertex-connection number of graphs
• Parity vertex colorings of binomial trees

Cited In (11)

• Conflict-free (vertex)-connection numbers of graphs with small diameters
• Title not available (Why is that?)
• Conflict-free connection number of graphs with four bridges
• Interdicting facilities in tree networks
• Some results on strong conflict-free connection number of graphs
• Conflict-free connection number and independence number of a graph
• Construction of the developing connecting tree
• Conflict-free vertex-connections of graphs
• Strong conflict-free connection of graphs
• A survey on conflict-free connection coloring of graphs
• Title not available (Why is that?)

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)