zbMATH — the first resource for mathematics

Multigraphs with \(\Delta \geq 3\) are totally-\((2\Delta - 1)\)-choosable. (English) Zbl 1221.05133
Summary: 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 \(\Delta (G)\), then \(T(G)\) is \((2\Delta (G) - 1)\)-choosable. We give a linear-time algorithm that produces such a coloring. The best previous general upper bound for \(\Delta (G) > 3\) was \(\lfloor{\frac{3}{2}\Delta(G)+2 \rfloor}\), by O. V. Borodin, A. V. Kostochka, and D. R. Woodall [“List edge and list total colourings of multigraphs,” J. Comb. Theory, Ser. B 71, No.2, 184–204 (1997; Zbl 0876.05032)]. When \(\Delta (G) = 4\), our algorithm gives a better upper bound. When \(\Delta (G)\in \{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 [loc. cit.]).
05C15 Coloring of graphs and hypergraphs
Full Text: DOI arXiv
[1] Borodin, O.V., Kostochka, A.V., Woodall, D.R.: List Edge and List Total Colourings of Multigraphs. J. Combin. Theory Ser. B 71, 184–204 (1997) · Zbl 0876.05032
[2] Erdös, P., Rubin, A.L., Taylor, H.: Choosability in graphs. Congr. Numer. 26, 125–157 (1979)
[3] Galvin, F.: The list chromatic index of a bipartite multigraph. J. Combin. Theory Ser. B 63, 153–158 (1995) · Zbl 0826.05026
[4] Juvan, M., Mohar, B., Skrekovski, R.: List Total Colourings of Graphs. Combinatorics, Probability and Computing 7, 181–188 (1998) · Zbl 0911.05033
[5] Skulrattanakulchai, S., Gabow, H.N.: Coloring Algorithms on Subcubic Graphs. Internat. J. Found. Comput. Sci. 15 no. 1, 21–40 (2004) · Zbl 1101.68735
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.