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

DOI10.1007/S00373-008-0817-5MaRDI QIDQ1043786zbMATH OpenOpenAlexFDO

Authors Daniel W. Cranston

Publication date 9 December 2009

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

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

zbMATH Keywords

multigraphlist coloringchoosabilitytotal coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.).

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

Cites work

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

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)