Planar graphs without 5-cycles or without 6-cycles
type: Item
instance of: scholarly article
title: Planar graphs without 5-cycles or without 6-cycles
zbMATH Open document ID: 1186.05043
author: Qin Ma
author: Jian-Liang Wu
author: Xiao Yu
published in: Discrete Mathematics
publication date: 2009-06-23T00:00:00Z
review text: 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.
reviewed by: Dan S. Archdeacon
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5569044
zbMATH Keywords: planarity
zbMATH Keywords: discharging
zbMATH Keywords: list colorings
zbMATH Keywords: arboricity
zbMATH Keywords: list edge chromatic number
zbMATH Keywords: list total chromatic number
zbMATH Keywords: linear k-arboricity
MaRDI profile type: Publication
full work available at URL: j.disc.2008.07.033
OpenAlex ID: W2088603101
Wikidata QID: Q62838274
cites work: Q4222072
cites work: On linear k-arboricity
cites work: Q5422499
cites work: List edge and list total colourings of multigraphs
cites work: Algorithmic aspects of linear \(k\)-arboricity
cites work: Linear \(k\)-arboricities on trees
cites work: Q4017192
cites work: Q4326214
cites work: Some problems about linear arboricity
cites work: List edge and list total colorings of planar graphs without 4-cycles
cites work: On the linear \(k\)-arboricity of cubic graphs
cites work: List Total Colourings of Graphs
cites work: The linear 2-arboricity of planar graphs
cites work: Q3415464
cites work: Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
DOI: 10.1016/J.DISC.2008.07.033
description: scientific article; zbMATH DE number 5569044