Characterization of (2m,m)-paintable graphs

MaRDI QIDQ2344816zbMATH OpenFDO

Authors Thomas Mahoney, Jixian Meng, Xuding Zhu

Publication date 18 May 2015

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

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p14

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

fractional paint numberon-line List colouringpaint numberpainting game

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

Summary: In this paper, we prove that for any graph \(G\) and any positive integer \(m\), \(G\) is \((2m,m)\)-paintable if and only if \(G\) is 2-paintable. It was asked by \textit{X. Zhu} [Electron. J. Comb. 16, No. 1, Research Paper R127, 16 p. (2009; Zbl 1186.05061)] whether \(k\)-paintable graphs are \((km,m)\)-paintable for any positive integer \(m\). Our result answers this question in the affirmative for \(k=2\).

Recommendations

• Strengthening \((a,b)\)-choosability results to \((a,b)\)-paintability
• scientific article; zbMATH DE number 1743975
• scientific article; zbMATH DE number 2170344
• Every planar graph is 1-defective \((9,2)\)-paintable
• scientific article; zbMATH DE number 908794

Cites work

• Choosability and fractional chromatic numbers
• Critically paintable, choosable or colorable graphs
• Graph colorings with local constraints -- a survey
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 908794 (Why is no real title available?)
• Mr. Paint and Mrs. Correct
• Mr. Paint and Mrs. Correct go fractional
• On-line list colouring of graphs
• Three topics in online list coloring

Cited in

(5)

• Strengthening \((a,b)\)-choosability results to \((a,b)\)-paintability
• scientific article; zbMATH DE number 1743975 (Why is no real title available?)
• scientific article; zbMATH DE number 2170344 (Why is no real title available?)
• The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs
• Paintability of complete bipartite graphs

This page was built for publication: Characterization of \((2m,m)\)-paintable graphs

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