Vehicular ad-hoc networks (VANETs), as an important component of intelligent transportation systems (ITS), have been attracting more and more research interests for their various promising applications. Although various MAC protocols have been proposed, efficient medium access remains a significant challenge in VANETs, especially in improving the network throughput in heavy traffic vehicular networks. In this paper, we propose an interference-free graph based time division

multiple access (IG-TDMA) protocol for VANETs. In the proposed protocol, roadside units (RSUs), as centralized controllers, collect the information from active vehicles and construct the interference-free graph based on the vehicle locations and a preset interference-free threshold. We further propose a communication link selection algorithm, which can help the RSUs

make efficient and effective scheduling decisions with high spatial reuse efficiency and low computational complexity. Simulations verify that the proposed IG-TDMA protocol can improve the network performance significantly compared with the IEEE 802.11p CSMA/CA based EDCA scheme and traditional TDMA protocol.