On (3, 1)^-choosability of planar graphs without adjacent short cycles

DOI10.1016/J.DAM.2013.09.009MaRDI QIDQ741735zbMATH OpenOpenAlexFDO

Authors Min Chen, André Raspaud

Publication date 12 September 2014

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

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

zbMATH Keywords

cycleplanar graphsimproper choosability

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: A list assignment of a graph $G$ is a function $L$ that assigns a list $L(v)$ of colors to each vertex $vinV(G)$. An $(L,d{)}^{\ast }$-coloring is a mapping $pi$ that assigns a color $pi(v)inL(v)$ to each vertex $vinV(G)$ so that at most $d$ neighbors of $v$ receive color $pi(v)$. A graph $G$ is said to be $(k,d{)}^{\ast }$-choosable if it admits an $(L,d{)}^{\ast }$-coloring for every list assignment $L$ with $|L(v)|gek$ for all $vinV(G)$. In 2001, Lih et al. cite{LSWZ-01} proved that planar graphs without 4- and $l$-cycles are $(3,1{)}^{\ast }$-choosable, where $lin5,6,7$. Later, Dong and Xu cite{DX-09} proved that planar graphs without 4- and l-cycles are $(3,1{)}^{\ast }$-choosable, where $lin8,9$. There exist planar graphs containing 4-cycles that are not $(3,1{)}^{\ast }$-choosable (Crown, Crown and Woodall, 1986 cite{CCW-86}). This partly explains the fact that in all above known sufficient conditions for the $(3,1{)}^{\ast }$-choosability of planar graphs the 4-cycles are completely forbidden. In this paper we allow 4-cycles nonadjacent to relatively short cycles. More precisely, we prove that every planar graph without 4-cycles adjacent to 3- and 4-cycles is $(3,1{)}^{\ast }$-choosable. This is a common strengthening of all above mentioned results. Moreover as a consequence we give a partial answer to a question of Xu and Zhang cite{XZ-07} and show that every planar graph without 4-cycles is $(3,1{)}^{\ast }$-choosable.

Recommendations

• A \((3,1)^\ast\)-choosable theorem on planar graphs
• scientific article; zbMATH DE number 6873968
• \((4,1)^*\)-choosability of planar graphs
• Improper choosability of planar graphs without 4-cycles
• On choosability with separation of planar graphs without adjacent short cycles

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• A Grötzsch-Type Theorem for List Colourings with Impropriety One
• A \((3,1)^*\)-choosable theorem on toroidal graphs
• A note on list improper coloring of plane graphs
• A note on list improper coloring planar graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Every toroidal graph without adjacent triangles is \((4,1)^{*}\)-choosable
• List Improper Colourings of Planar Graphs
• List improper colorings of planar graphs with prescribed girth
• Multicriterial graph problems with MAXMIN criterion
• Planar graphs are 1-relaxed, 4-choosable

Cited in

(6)

• (3, 1)-choosability of toroidal graphs with some forbidden short cycles
• Sufficient conditions on planar graphs to have a relaxed DP-3-coloring
• \((3, 1)^*\)-choosability of graphs of nonnegative characteristic without intersecting short cycles
• The use of Euler's formula in (3,1)*-list-coloring
• A \((3,1)^\ast\)-choosable theorem on planar graphs
• Acyclic improper choosability of subcubic graphs

This page was built for publication: On \((3, 1)^\ast\)-choosability of planar graphs without adjacent short cycles

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