Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Combinatorial Bounds for Conflict-free Coloring on Open Neighborhoods   In an undirected graph $G$, a conflict-free coloring with respect to open
neighborhoods (denoted by CFON coloring) is an assignment of colors to the
vertices such that every vertex has a uniquely colored vertex in its open
neighborhood. The minimum number of colors required for a CFON coloring of $G$
is the CFON chromatic number of $G$, denoted by $\chi_{ON}(G)$.
  The decision problem that asks whether $\chi_{ON}(G) \leq k$ is NP-complete.
We obtain the following results:
  * Bodlaender, Kolay and Pieterse [WADS 2019] showed the upper bound
$\chi_{ON}(G)\leq {\sf fvs}(G)+3$, where ${\sf fvs}(G)$ denotes the size of a
minimum feedback vertex set of $G$. We show the improved bound of
$\chi_{ON}(G)\leq {\sf fvs}(G)+2$, which is tight, thereby answering an open
question in the above paper.
  * We study the relation between $\chi_{ON}(G)$ and the pathwidth of the graph
$G$, denoted ${\sf pw}(G)$. The above paper from WADS 2019 showed the upper
bound $\chi_{ON}(G) \leq 2{\sf tw}(G)+1$ where ${\sf tw}(G)$ stands for the
treewidth of $G$. This implies an upper bound of $\chi_{ON}(G) \leq 2{\sf
pw}(G)+1$. We show an improved bound of $\chi_{ON}(G) \leq \lfloor
\frac{5}{3}({\sf pw}(G)+1) \rfloor$.
  * We prove new bounds for $\chi_{ON}(G)$ with respect to the structural
parameters neighborhood diversity and distance to cluster, improving existing
results.
  * We also study the partial coloring variant of the CFON coloring problem,
which allows vertices to be left uncolored. Let $\chi^*_{ON}(G)$ denote the
minimum number of colors required to color $G$ as per this variant. Abel et.
al. [SIDMA 2018] showed that $\chi^*_{ON}(G) \leq 8$ when $G$ is planar. They
asked if fewer colors would suffice for planar graphs. We answer this question
by showing that $\chi^*_{ON}(G) \leq 5$ for all planar $G$.
  All our bounds are a result of constructive algorithmic procedures.

19
The categories of this paper are: eess
15
The categories of this paper are: nucl-ex
8
The categories of this paper are: hep-ex
18
The categories of this paper are: econ
29
The categories of this paper are: funct-an
35
The categories of this paper are: mtrl-th
9
The categories of this paper are: nlin
20
The categories of this paper are: acc-phys
36
The categories of this paper are: cmp-lg
30
The categories of this paper are: q-alg
32
The categories of this paper are: atom-ph
16
The categories of this paper are: stat
33
The categories of this paper are: plasm-ph
17
The categories of this paper are: q-fin
25
The categories of this paper are: patt-sol
7
The categories of this paper are: hep-th