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/

Zendy Plus

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

Zendy Tools

Zendy Open

A $K_3$-WORM coloring of a graph $G$ is an assignment of colors to thevertices in such a way that the vertices of each $K_3$-subgraph of $G$ getprecisely two colors. We study graphs $G$ which admit at least one suchcoloring. We disprove a conjecture of Goddard et al. [Congr. Numer., 219 (2014)161--173] who asked whether every such graph has a $K_3$-WORM coloring with twocolors. In fact for every integer $k\ge 3$ there exists a $K_3$-WORM colorablegraph in which the minimum number of colors is exactly $k$. There also exist$K_3$-WORM colorable graphs which have a $K_3$-WORM coloring with two colorsand also with $k$ colors but no coloring with any of $3,\dots,k-1$ colors. Wealso prove that it is NP-hard to determine the minimum number of colors andNP-complete to decide $k$-colorability for every $k \ge 2$ (and remainsintractable even for graphs of maximum degree 9 if $k=3$). On the other hand,we prove positive results for $d$-degenerate graphs with small $d$, alsoincluding planar graphs. Moreover we point out a fundamental connection withthe theory of the colorings of mixed hypergraphs. We list many open problems atthe end.

$K_3$-WORM colorings of graphs: Lower chromatic number and gaps in the chromatic spectrum