Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs

DOI10.1016/j.aml.2011.08.006zbMath1243.05130OpenAlexW2047875736MaRDI QIDQ427574

Baoyindureng Wu, Xing-Chao Deng, Kai-Nan Xiang

Publication date: 14 June 2012

Published in: Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aml.2011.08.006

zbMATH Keywords

rainbow connection numberrainbow coloringmaximal cardinality searchmaximal outerplanar graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Related Items (5)

Rainbow connections for outerplanar graphs with diameter 2 and 3 ⋮ Strong rainbow connection numbers of toroidal meshes ⋮ An integer program and new lower bounds for computing the strong rainbow connection numbers of graphs ⋮ On the general position numbers of maximal outerplane graphs ⋮ Algorithm on rainbow connection for maximal outerplanar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rainbow connection number and connected dominating sets
• Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs
• Rainbow connection in graphs
• Rainbow Connection in Graphs with Minimum Degree Three
• Hardness and Algorithms for Rainbow Connectivity

This page was built for publication: Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs