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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

For graphs $G$ and $H$, an $H$-coloring of $G$ is an edge-preserving mappingfrom $V(G)$ to $V(H)$. In the $H$-Coloring problem the graph $H$ is fixed andwe ask whether an instance graph $G$ admits an $H$-coloring. A generalizationof this problem is $H$-ColoringExt, where some vertices of $G$ are alreadymapped to vertices of $H$ and we ask if this partial mapping can be extended toan $H$-coloring.  We study the complexity of variants of $H$-Coloring in $F$-free graphs, i.e.,graphs excluding a fixed graph $F$ as an induced subgraph. For integers $a,b,c\geq 1$, by $S_{a,b,c}$ we denote the graph obtained by identifying oneendvertex of three paths on $a+1$, $b+1$, and $c+1$ vertices, respectively. Forodd $k \geq 5$, by $W_k$ we denote the graph obtained from the $k$-cycle byadding a universal vertex.  As our main algorithmic result we show that $W_5$-ColoringExt ispolynomial-time solvable in $S_{2,1,1}$-free graphs. This result exhibits aninteresting non-monotonicity of $H$-ColoringExt with respect to taking inducedsubgraphs of $H$. Indeed, $W_5$ contains a triangle, and $K_3$-Coloring, i.e.,classical 3-coloring, is NP-hard already in claw-free (i.e., $S_{1,1,1}$-free)graphs.  Our algorithm is based on two main observations:  1. $W_5$-ColoringExt in $S_{2,1,1}$-free graphs can be in polynomial timereduced to a variant of the problem of finding an independent set intersectingall triangles, and  2. the latter problem can be solved in polynomial time in $S_{2,1,1}$-freegraphs.  We complement this algorithmic result with several negative ones. Inparticular, we show that $W_5$-ColoringExt is NP-hard in $S_{3,3,3}$-freegraphs. This is again uncommon, as usually problems that are NP-hard in$S_{a,b,c}$-free graphs for some constant $a,b,c$ are already hard in claw-freegraphs.

Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws