Multigraphs with 3 are totally-(2 - 1)-choosable

DOI10.1007/S00373-008-0817-5zbMATH Open1221.05133arXiv1308.3038OpenAlexW2069022115MaRDI QIDQ1043786FDOQ1043786

Authors: Daniel W. Cranston 

Publication date: 9 December 2009

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: The emph{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 $(2Delta(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 $floorfrac32Delta(G)+2$, by Borodin et al. When $Delta(G)=4$, our algorithm gives a better upper bound. When $Delta(G)in3,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.).

Full work available at URL: https://arxiv.org/abs/1308.3038

Recommendations

• List Total Colourings of Graphs
• List edge and list total colourings of multigraphs
• Every planar graph with Δ ${\rm{\Delta }}$ ⩾ 8 is totally (Δ+2) $({\rm{\Delta }}+2)$‐choosable
• Some totally 4-choosable multigraphs
• scientific article; zbMATH DE number 798659

zbMATH Keywords

multigraphlist coloringchoosabilitytotal coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• List edge and list total colourings of multigraphs
• The list chromatic index of a bipartite multigraph
• List Total Colourings of Graphs
• COLORING ALGORITHMS ON SUBCUBIC GRAPHS

Cited In (1)

• Every graph is \((2,3)\)-choosable

This page was built for publication: Multigraphs with \(\Delta \geq 3\) are totally-\((2\Delta - 1)\)-choosable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1043786)