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

We present fixed parameter tractable algorithms for the conflict-freecoloring problem on graphs. Given a graph $G=(V,E)$, \emph{conflict-freecoloring} of $G$ refers to coloring a subset of $V$ such that for every vertex$v$, there is a color that is assigned to exactly one vertex in the closedneighborhood of $v$. The \emph{k-Conflict-free Coloring} problem is to decidewhether $G$ can be conflict-free colored using at most $k$ colors. This problemis NP-hard even for $k=1$ and therefore under standard complexity theoreticassumptions, FPT algorithms do not exist when parameterised by the solutionsize. We consider the \emph{k-Conflict-free Coloring} problem parameterised bythe treewidth of the graph and show that this problem is fixed parametertractable. We also initiate the study of \emph{Strong Conflict-free Coloring}of graphs. Given a graph $G=(V,E)$, \emph{strong conflict-free coloring} of $G$refers to coloring a subset of $V$ such that every vertex $v$ has at least onecolored vertex in its closed neighborhood and moreover all the colored verticesin $v$'s neighborhood have distinct colors. We show that this problem is in FPTwhen parameterised by both the treewidth and the solution size. We furtherapply these algorithms to get efficient algorithms for a geometric problemnamely the Terrain Guarding problem, when parameterised by a structuralparameter.

FPT Algorithms for Conflict-free Coloring of Graphs and Chromatic Terrain Guarding