A (k, 2)-track layout of a graph G consists of a 2-track assignment of G and an edge k-coloring of G with no monochromatic X-crossing. This paper studies the problem of (k, 2)-track layout of bipartite graph subdivisions. Recently V. Dujmovic and D.R. Wood showed that for every integer d ≥ 2, every graph G with n vertices has a (d + 1,2)-track layout of a subdivision of G with 4log_d qn(G) + 3 division vertices per edge, where qn(G) is the queue number of G. This paper improves their result for the case of bipartite graphs, and shows that for every integer d ≥ 2, every bipartite graph G_(m,n) has a (d + 1,2)-track layout of a subdivision of G_(m,n) with 2log_d n - 1 division vertices per edge, where m and n are numbers of vertices of the partite sets of G_(m,n) with m ≥ n.
展开▼
