List edge-coloring and total coloring in graphs of low treewidth

DOI10.1002/JGT.21874MaRDI QIDQ2800543zbMATH OpenOpenAlexFDO

Authors Henning Bruhn, Richard Lang, Maya Stein

Publication date 15 April 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

total colouringlist colouringtree width

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Vertex degrees (05C07) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)

Abstract: We prove that the list chromatic index of a graph of maximum degree $Delta$ and treewidth $leqsqrt2Delta-3$ is $Delta$; and that the total chromatic number of a graph of maximum degree $Delta$ and treewidth $leqDelta/3+1$ is $Delta+1$. This improves results by Meeks and Scott.

Recommendations

• Chromatic index, treewidth and maximum degree
• On the Complexity of Some Colorful Problems Parameterized by Treewidth
• On the complexity of some colorful problems parameterized by treewidth
• Chromatic index, treewidth and maximum degree
• Neighbor sum distinguishing total coloring of graphs with bounded treewidth

Cites work

• A bound on the total chromatic number
• Edge-Coloring Partialk-Trees
• Graph theory
• List edge and list total colourings of multigraphs
• List edge-colorings of series-parallel graphs
• List-colourings of graphs
• SOME UNSOLVED PROBLEMS IN GRAPH THEORY
• The average degree of a multigraph critical with respect to edge or total choosability
• The list chromatic index of a bipartite multigraph
• The total chromatic number of any multigraph with maximum degree five is at most seven
• Total colorings of degenerate graphs

Cited in

(11)

• On the linear arboricity of graphs with treewidth at most four
• Total colorings-a survey
• Neighbor sum distinguishing total coloring of graphs with bounded treewidth
• A note on total and list edge-colouring of graphs of tree-width 3
• Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
• Efficiently list-edge coloring multigraphs asymptotically optimally
• Chromatic index, treewidth and maximum degree
• Proof of the list edge coloring conjecture for complete graphs of prime degree
• The parameterised complexity of list problems on graphs of bounded treewidth
• Chromatic index, treewidth and maximum degree
• An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree

This page was built for publication: List edge-coloring and total coloring in graphs of low treewidth

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