Defective 3-paintability of planar graphs

MaRDI QIDQ1753126zbMATH OpenFDO

Authors Grzegorz Gutowski, Ming Han, Tomasz Krawczyk, Xuding Zhu

Publication date 25 May 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.01599, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p34

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

planar graph\(d\)-defective painting gamedefective paintability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A $d$-defective $k$-painting game on a graph $G$ is played by two players: Lister and Painter. Initially, each vertex is uncolored and has $k$ tokens. In each round, Lister marks a chosen set $M$ of uncolored vertices and removes one token from each marked vertex. In response, Painter colors vertices in a subset $X$ of $M$ which induce a subgraph $G[X]$ of maximum degree at most $d$. Lister wins the game if at the end of some round there is an uncolored vertex that has no more tokens left. Otherwise, all vertices eventually get colored and Painter wins the game. We say that $G$ is $d$-defective $k$-paintable if Painter has a winning strategy in this game. In this paper we show that every planar graph is 3-defective 3-paintable and give a construction of a planar graph that is not 2-defective 3-paintable.

Recommendations

• Every planar graph is 1-defective \((9,2)\)-paintable
• Locally planar graphs are 2-defective 4-paintable
• scientific article; zbMATH DE number 1250667
• A simple competitive graph coloring algorithm. III
• 3-paintability of planar graphs

Cites work

• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Every planar graph is 5-choosable
• List Improper Colourings of Planar Graphs
• List colourings of planar graphs
• Locally planar graphs are 2-defective 4-paintable
• Mr. Paint and Mrs. Correct
• On-line list colouring of graphs
• Planar graphs are 1-relaxed, 4-choosable

Cited in

(6)

• Decomposing planar graphs into graphs with degree restrictions
• The Alon-Tarsi number of planar graphs without cycles of lengths 4 and \(l\)
• The Alon-Tarsi number of a planar graph minus a matching
• Weak (2, 3)-decomposition of planar graphs
• Every planar graph is 1-defective \((9,2)\)-paintable
• Locally planar graphs are 2-defective 4-paintable

This page was built for publication: Defective 3-paintability of planar graphs

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