Every planar graph is 1-defective (9,2)-paintable

DOI10.1016/J.DAM.2021.02.008MaRDI QIDQ2656972zbMATH OpenOpenAlexFDO

Authors Ming Han, H. A. Kierstead, Xuding Zhu

Publication date 17 March 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

planar graph\(d\)-defective painting gameon-line list coloring

Mathematics Subject Classification ID

2-person games (91A05) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: Assume $L$ is a $k$-list assignment of a graph $G$. A $d$-defective $m$-fold $L$-colouring $phi$ of $G$ assigns to each vertex $v$ a set $phi(v)$ of $m$ colours, so that $phi(v)subseteqL(v)$ for each vertex $v$, and for each colour $i$, the set $v:iinphi(v)$ induces a subgraph of maximum degree at most $d$. In this paper, we consider on-line list $d$-defective $m$-fold colouring of graphs, where the list assignment $L$ is given on-line, and the colouring is constructed on-line. To be precise, the $d$-defective $(k,m)$-painting game on a graph $G$ is played by two players: Lister and Painter. Initially, each vertex has $k$ tokens and is uncoloured. In each round, Lister chooses a set $M$ of vertices and removes one token from each chosen vertex. Painter colours a subset $X$ of $M$ which induces a subgraph $G[X]$ of maximum degree at most $d$. A vertex $v$ is fully coloured if $v$ has received $m$ colours. Lister wins if at the end of some round, there is a vertex with no more tokens left and is not fully coloured. Otherwise, at some round, all vertices are fully coloured and Painter wins. We say $G$ is $d$-defective $(k,m)$-paintable if Painter has a winning strategy in this game. This paper proves that every planar graph is $1$-defective $(9,2)$-paintable.

Recommendations

• Defective 3-paintability of planar graphs
• Locally planar graphs are 2-defective 4-paintable
• scientific article; zbMATH DE number 1250667
• scientific article; zbMATH DE number 1833073
• The Alon-Tarsi number of a planar graph minus a matching

Cites work

• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A (<5)-Colour Theorem for Planar Graphs
• Choosability and fractional chromatic numbers
• Defective 3-paintability of planar graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Every planar graph is 5-choosable
• List Improper Colourings of Planar Graphs
• Locally planar graphs are 2-defective 4-paintable
• Locally planar graphs are 5-paintable
• Mr. Paint and Mrs. Correct
• Mr. Paint and Mrs. Correct go fractional
• Multiple list colouring of planar graphs
• On-line 3-choosable planar graphs
• Planar graphs are 1-relaxed, 4-choosable
• Planar graphs are \(9/2\)-colorable
• The Alon-Tarsi number of a planar graph minus a matching

Cited in

(4)

• Multiple DP-coloring of planar graphs without 3-cycles and normally adjacent 4-cycles
• Characterization of \((2m,m)\)-paintable graphs
• Locally planar graphs are 2-defective 4-paintable
• Defective 3-paintability of planar graphs

This page was built for publication: Every planar graph is 1-defective \((9,2)\)-paintable

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