English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Proper conflict-free coloring is an intermediate notion between propercoloring of a graph and proper coloring of its square. It is a proper coloringsuch that for every non-isolated vertex, there exists a color appearing exactlyonce in its (open) neighborhood. Typical examples of graphs with large properconflict-free chromatic number include graphs with large chromatic number andbipartite graphs isomorphic to the $1$-subdivision of graphs with largechromatic number. In this paper, we prove two rough converse statements thathold even in the list-coloring setting. The first is for sparse graphs: forevery graph $H$, there exists an integer $c_H$ such that every graph with nosubdivision of $H$ is (properly) conflict-free $c_H$-choosable. The secondapplies to dense graphs: every graph with large conflict-free choice numbereither contains a large complete graph as an odd minor or contains a bipartiteinduced subgraph that has large conflict-free choice number. These give twoincomparable (partial) answers of a question of Caro, Petru\v{s}evski and\v{S}krekovski. We also prove quantitatively better bounds for minor-closedfamilies, implying some known results about proper conflict-free coloring andodd coloring in the literature. Moreover, we prove that every graph withlayered treewidth at most $w$ is (properly) conflict-free $(8w-1)$-choosable.This result applies to $(g,k)$-planar graphs, which are graphs whose coloringproblems have attracted attention recently.

Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth