Defective and clustered choosability of sparse graphs

DOI10.1017/S0963548319000063zbMATH Open1436.05038arXiv1806.07040OpenAlexW2887773522WikidataQ128056358 ScholiaQ128056358MaRDI QIDQ5222556FDOQ5222556

Authors: Kevin Hendrey, David R. Wood 

Publication date: 6 April 2020

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

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.

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

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

zbMATH Keywords

choosability of graphs

Mathematics Subject Classification ID

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

Cites Work

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

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)