Defective and clustered choosability of sparse graphs

DOI10.1017/S0963548319000063MaRDI QIDQ5222556zbMATH OpenOpenAlexWikidataFDO

Authors Kevin Hendrey, David R. Wood

Publication date 6 April 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

choosability of graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Abstract: An (improper) graph colouring has "defect" $d$ if each monochromatic subgraph has maximum degree at most $d$, and has "clustering" $c$ if each monochromatic component has at most $c$ vertices. This paper studies defective and clustered list-colourings for graphs with given maximum average degree. We prove that every graph with maximum average degree less than $frac2d+2d+2k$ is $k$-choosable with defect $d$. This improves upon a similar result by Havet and Sereni [J. Graph Theory, 2006]. For clustered choosability of graphs with maximum average degree $m$, no $(1-epsilon)m$ bound on the number of colours was previously known. The above result with $d=1$ solves this problem. It implies that every graph with maximum average degree $m$ is $lfloorfrac34m+1floor$-choosable with clustering 2. This extends a result of Kopreski and Yu [Discrete Math., 2017] to the setting of choosability. We then prove two results about clustered choosability that explore the trade-off between the number of colours and the clustering. In particular, we prove that every graph with maximum average degree $m$ is $lfloorfrac710m+1floor$-choosable with clustering $9$, and is $lfloorfrac23m+1floor$-choosable with clustering $O(m)$. As an example, the later result implies that every biplanar graph is 8-choosable with bounded clustering. This is the best known result for the clustered version of the earth-moon problem. The results extend to the setting where we only consider the maximum average degree of subgraphs with at least some number of vertices. Several applications are presented.

Recommendations

• Defective and clustered graph colouring
• Improper choosability of graphs and maximum average degree
• scientific article; zbMATH DE number 1250667
• Defective 2-colorings of sparse graphs
• Clustered 3-colouring graphs of bounded degree

Cites work

• scientific article; zbMATH DE number 3144962 (Why is no real title available?)
• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• A note on defective colorings of graphs in surfaces
• A note on vertex list colouring
• A relative of Hadwiger's conjecture
• Bounded size components -- partitions and transversals.
• Clustered colouring in minor-closed classes
• Coloring Ordinary Maps, Maps of Empires, and Maps of the Moon
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Defective 2-colorings of sparse graphs
• Defective and clustered graph colouring
• Defective choosability of graphs in surfaces
• Defective coloring revisited
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Defective colouring of graphs excluding a subgraph or minor
• Improper choosability of graphs and maximum average degree
• Improper coloring of graphs on surfaces
• Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
• Improper coloring of sparse graphs with a given girth. II: Constructions
• Improper colourings inspired by Hadwiger's conjecture
• Layouts of Expander Graphs
• Limits of near-coloring of sparse graphs
• List strong linear 2-arboricity of sparse graphs
• Maximum average degree and relaxed coloring
• More results on \(r\)-inflated graphs: arboricity, thickness, chromatic number and fractional chromatic number
• On 1-improper 2-coloring of sparse graphs
• Partitioning into graphs with only small components
• Planar graphs are 1-relaxed, 4-choosable
• The thickness of graphs: A survey
• Thickness-two graphs. II: More new nine-critical graphs, independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs
• Thickness‐two graphs part one: New nine‐critical graphs, permuted layer graphs, and Catlin's graphs
• Variations on Ringel's earth-moon problem
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most \(k\)
• \((k,1)\)-coloring of sparse graphs
• \((k,j)\)-coloring of sparse graphs

Cited in

(10)

• Clustered 3-colouring graphs of bounded degree
• Defective and clustered graph colouring
• On 2-defective DP-colorings of sparse graphs
• Clustered coloring of graphs with bounded layered treewidth and bounded degree
• Colouring strong products
• Sparse critical graphs for defective DP-colorings
• On two problems of defective choosability of graphs
• Clustered variants of Hajós' conjecture
• Defective DP-colorings of sparse multigraphs
• Defective DP-colorings of sparse simple graphs

This page was built for publication: Defective and clustered choosability of sparse graphs

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