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

\(d\)-defective painting gamedefective paintabilityplanar graph

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.

Review text

Summary: 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

• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Every planar graph is 5-choosable
• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• List colourings of planar graphs
• List Improper 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

(7)

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

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)