Planar graphs without 5-cycles or without 6-cycles (Q1025913): Difference between revisions

Let \(G\) be a graph without 5-cycles or 6-cycles. The authors show that there is either an edge \(uv\) with \(\deg(u) + \deg(v) \leq 9\), or a cycle of even length such that every other vertex is of degree 2. The list-edge-chromatic number is the smallest \(k\) such that if each edge is assigned a set of \(k\) colors, there is always an edge-coloring using colors from each edge's list such that adjacent edges receive distinct colors. The list-total-chromatic number is the smallest \(k\) such that if each vertex and each edge is assigned a set of \(k\) colors, there is always a coloring of the edges and vertices from each's list such that adjacent or incident elements receive distinct colors. The linear \(k\)-arboricity of a graph is the smallest \(m\) such that the edges of \(G\) can be partitioned into \(m\) parts, each part having components that are paths of length at most \(k\). The authors use the first result to show {\parindent=7mm \begin{itemize}\item[(1)]the linear 2-arboricity of \(G\) is at most \(\lceil (\Delta(G)+1)/2\rceil + 6\), \item[(2)]the list-total-chromatic number is \(\Delta(G)+1\) if \(\Delta(G) \geq 8\), and \item[(3)]The list-edge-chromatic number is \(\Delta(G)\) if \(\Delta(G) \geq 8\). \end{itemize}} The advantage of considering graphs without cycles of length 5 or 6 is to restrict how cycles of length 3 and 4 can intersect. This allows the authors to use discharging methods as if the graph were of large girth.