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

DOI10.1002/JGT.21874zbMATH Open1339.05114arXiv1311.2969OpenAlexW2144392803MaRDI QIDQ2800543FDOQ2800543

Authors: Henning Bruhn, Richard Lang, Maya Stein 

Publication date: 15 April 2016

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

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.

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

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

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)

Cites Work

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

Cited In (11)

• On the linear arboricity of graphs with treewidth at most four
• Total colorings-a survey
• Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
• Neighbor sum distinguishing total coloring of graphs with bounded treewidth
• A note on total and list edge-colouring of graphs of tree-width 3
• 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)