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

DOI10.1016/J.AML.2011.08.006zbMATH Open1243.05130OpenAlexW2047875736MaRDI QIDQ427574FDOQ427574

Authors: Xingchao Deng, Kai-Nan Xiang, Baoyindureng Wu 

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

Recommendations

• Rainbow connections for outerplanar graphs with diameter 2 and 3
• Algorithm on rainbow connection for maximal outerplanar graphs
• Hardness and algorithms for rainbow connection
• Rainbow connectivity: hardness and tractability

zbMATH Keywords

rainbow connection numberrainbow coloringmaximal cardinality searchmaximal outerplanar graph

Mathematics Subject Classification ID

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

Cites Work

• Rainbow connection number and connected dominating sets
• Rainbow connection in graphs
• Rainbow connection in graphs with minimum degree three
• Hardness and Algorithms for Rainbow Connectivity
• Title not available (Why is that?)
• Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• Title not available (Why is that?)
• Strong rainbow connection numbers of toroidal meshes
• Rainbow connections for outerplanar graphs with diameter 2 and 3
• 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

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

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