Multigraphs with 3 are Totally-(2-1)-Choosable
Daniel W. Cranston · 2013
The total graph T(G) of a multigraph G has as its vertices the set of edges and vertices of G and has an edge between two vertices if their corresponding elements are either adjacent or incident in G. We show that if G has maximum degree ∆(G), then T(G) is (2∆(G) − 1)-choosable. We give a linear-time algorithm that produces such a coloring. The best previous general upper bound for ∆(G)> 3 was ⌊ 3 ∆(G) + 2⌋, by Borodin et al. When ∆(G) = 4, our algorithm gives a better upper bound. When 2 ∆(G) ∈ {3, 5, 6}, our algorithm matches the best known bound. However, because our algorithm is significantly simpler, it runs in linear time (unlike the algorithm of Borodin et al.). Throughout this paper, G is a connected multigraph (if G is not connected, we can color each component independently). For convenience, we refer to edges and vertices as elements of the graph. The total graph T(G) of a graph G has as its vertices the set of edges and vertices of G and has an edge between two vertices if their corresponding elements are either adjacent or incident in G. Let L be an assignment of lists to the vertices of a graph G. If G has a proper coloring such that each vertex v gets a color from its list L(v),