Localizing an autonomous vehicle in real-time is critical for robust autonomous driving. As a standard approach, the map-based localization is robust and fast; however, it is expensive to create and maintain a large-scale high-definition map. In this paper, we propose an online localization technique based on the vehicle-to-vehicle communication and traffic landmark detection; called collaborative localization. This can potentially serve as a new complement to the standard localization solutions. We theoretically show that multiple vehicles with multiple traffic landmarks would significantly improve the localization performance. We then propose a practical algorithm, which leverages graph matching to handle practical issues, such as traffic landmark association. The experimental results validate the potential of the proposed methods.