The conflict-free closed neighborhood (CFCN^*) chromatic number of a graph G = (V,E) is the smallest positive integer k for which there exists a coloring of a subset of vertices using k colors such that, for every vertex in V, there exists a color that appears exactly once in its closed neighborhood. The conflict-free open neighborhood (CFON^*) chromatic number is defined analogously. In this paper, we study "list variants" of the above-mentioned coloring parameters. The conflict-free closed neighborhood (CFCN^*) choice number of a graph G = (V,E) is the smallest positive integer k such that for every assignment of lists of size k to its vertices, there exists a coloring of a subset of vertices, say V', in which (i) every vertex in V' receives a color from its list, and (ii) for every vertex in V there exists some color that appears exactly once in its closed neighborhood. The conflict-free open neighborhood (CFON^*) choice number is defined analogously. Dębski and Przybyło [Journal of Graph Theory, 2022] showed that for any graph G with maximum degree Δ, the CFCN^* chromatic number of its line graph is O(ln Δ). This result was later extended to claw-free graphs by Bhyravarapu et al. [Journal of Graph Theory, 2023], who proved that every K_{1,k}-free graph G admits a CFCN^* coloring using O(kln Δ) colors. In this paper, we generalize this result to the list setting and show that every K_{1,k}-free graph G has a CFCN^* choice number of O(kln Δ). Further, we answer some questions concerning the hardness of computing CFCN^*/CFON^* choice numbers posed by Gupta and Mathew [SOFSEM, 2026]; in particular, we show that it is NP-hard to determine whether the CFCN^*/CFON^* choice number a graph is equal to k, for k = 1,2.

We give an algorithm that finds a zero forcing set which approximates the optimal size by a factor of pw ( G ) + 1 , where pw ( G ) is the pathwidth of G . The algorithm requires a path decomposition of G , and given this it runs in O ( n m ) time, where n and m are the order and size of the graph, respectively. This is the first zero forcing algorithm with a guarantee on both the approximation ratio and on the run-time. As a corollary, we obtain a new upper bound on the zero forcing number in terms of the fort number and the pathwidth. The algorithm is based on a correspondence between zero forcing sets and forcing arc sets. This correspondence leads to a new bound on the zero forcing number in terms of vertex cuts, and to new, short proofs for known bounds on the zero forcing number.

We present a hypergraph coloring based approach to pliable index coding (PICOD). We represent the given PICOD problem using a hypergraph consisting ofmmessages as vertices and the request-sets of thenclients as hyperedges. Aconflict-free coloringof a hypergraph is an assignment of colors to its vertices so that each hyperedge contains a uniquely colored vertex. We show that various parameters arising out of conflict-free colorings (and some new variants) of the PICOD hypergraph result in new upper bounds for the optimal PICOD length. Using these new upper bounds, we show the existence of single-request PICOD schemes with lengthO(log2Γ), where Γ is the maximum number of hyperedges overlapping with any hyperedge. For thet-request PICOD scenario, we show the existence of PICOD schemes of length max(O(log Γ logm),O(tlogm)), under some mild conditions on the graph parameters. These results improve upon earlier work in general. We also show that our achievable lengths in thet-request case are asymptotically optimal, up to a multiplicative factor of logt. Our existence results are accompanied by randomized constructive algorithms, which have complexity polynomial in the parameters of the PICOD problem, in expectation or with high probability.

A Conflict-Free Open Neighborhood coloring, abbreviated CFON^* coloring, of a graph G = (V,E) using k colors is an assignment of colors from a set of k colors to a subset of vertices of V(G) such that every vertex sees some color exactly once in its open neighborhood. The minimum k for which G has a CFON^* coloring using k colors is called the CFON^* chromatic number of G, denoted by χ_{ON}^*(G). The analogous notion for closed neighborhood is called CFCN^* coloring and the analogous parameter is denoted by χ_{CN}^*(G). The problem of deciding whether a given graph admits a CFON^* (or CFCN^*) coloring that uses k colors is NP-complete. Below, we describe briefly the main results of this paper. - For k ≥ 3, we show that if G is a K_{1,k}-free graph then χ_{ON}^*(G) = O(k²log Δ), where Δ denotes the maximum degree of G. Dębski and Przybyło in [J. Graph Theory, 2021] had shown that if G is a line graph, then χ_{CN}^*(G) = O(log Δ). As an open question, they had asked if their result could be extended to claw-free (K_{1,3}-free) graphs, which are a superclass of line graphs. Since it is known that the CFCN^* chromatic number of a graph is at most twice its CFON^* chromatic number, our result positively answers the open question posed by Dębski and Przybyło. - We show that if the minimum degree of any vertex in G is Ω(Δ/{log^ε Δ}) for some ε ≥ 0, then χ_{ON}^*(G) = O(log^{1+ε}Δ). This is a generalization of the result given by Dębski and Przybyło in the same paper where they showed that if the minimum degree of any vertex in G is Ω(Δ), then χ_{ON}^*(G)= O(logΔ). - We give a polynomial time algorithm to compute χ_{ON}^*(G) for interval graphs G. This answers in positive the open question posed by Reddy [Theoretical Comp. Science, 2018] to determine whether the CFON^* chromatic number can be computed in polynomial time on interval graphs. - We explore biconvex graphs, a subclass of bipartite graphs and give a polynomial time algorithm to compute their CFON^* chromatic number. This is interesting as Abel et al. [SIDMA, 2018] had shown that it is NP-complete to decide whether a planar bipartite graph G has χ_{ON}^*(G) = k where k ∈ {1, 2, 3}.

In the pliable index coding (PICOD) problem, a server is to serve multiple clients, each of which possesses a unique subset of the complete message set as side information and requests a new message which it does not have. The goal of the server is to do this using as few transmissions as possible. This work presents a hypergraph coloring approach to the PICOD problem. A conflict-free coloring of a hypergraph is known from literature as an assignment of colors to its vertices so that each edge of the graph contains one uniquely colored vertex. For a given PICOD problem represented by a hypergraph consisting of messages as vertices and request-sets as edges, we present achievable PICOD schemes using conflict-free colorings of the PICOD hypergraph. Various graph theoretic parameters arising out of such colorings (and some new coloring variants) then give a number of upper bounds on the optimal PICOD length, which we study in this work. Our achievable schemes based on hypergraph coloring include scalar as well as vector linear PICOD schemes. For the scalar case, using the correspondence with conflict-free coloring, we show the existence of an achievable scheme which has length$O(\log^{2}\Gamma)$, where$\Gamma$refers to a parameter of the hypergraph that captures the maximum ‘incidence’ number of other edges on any edge. This result improves upon known achievability results in PICOD literature, in some parameter regimes.

The separation dimension of a graph $G$ is the smallest natural number $k$ for which the vertices of $G$ can be embedded in $\mathbb{R}^k$ such that any pair of disjoint edges in $G$ can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family $\mathcal{F}$ of total orders of the vertices of $G$ such that for any two disjoint edges of $G$, there exists at least one total order in $\mathcal{F}$ in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on $n$ vertices is $\Theta(\log n)$. In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree $d$ is at most $2^{9{log^{\star}}\!d} d$. We also demonstrate that the above bound is nearly tight by showing that, for every $d$, almost all $d$-regular graphs have separation dimension at least $\ceil{d/2}$.

We present two online algorithms for maintaining a topological order of a directed n -vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O( m 3/2 ) time. For sparse graphs ( m / n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O( n 5/2 ) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Ω( n 2 2 √2 lg n ) time by relating its performance to a generalization of the k -levels problem of combinatorial geometry. A completely different algorithm running in Θ( n 2 log n ) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

A k-box B=(R_1,R_2,...,R_k), where each R_i is a closed interval on the real line, is defined to be the Cartesian product R_1 X R_2 X ... X R_k. If each R_i is a unit length interval, we call B a k-cube. Boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as cub(G), is the minimum integer k such that G is an intersection graph of k-cubes. It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan. Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/0607092, 2006.] that, for a graph G with maximum degree \Delta, cub(G) <= \lceil 4(\Delta +1) ln n\rceil. In this paper we show that, for a k-degenerate graph G, cub(G) <= (k+2) \lceil 2e log n \rceil. Since k is at most \Delta and can be much lower, this clearly is a stronger result. We also give an efficient deterministic algorithm that runs in O(n^2k) time to output a 8k(\lceil 2.42 log n\rceil + 1) dimensional cube representation for G. The crossing number of a graph G, denoted as CR(G), is the minimum number of crossing pairs of edges, over all drawings of G in the plane. An important consequence of the above result is that if the crossing number of a graph G is t, then box(G) is O(t^{1/4}{\lceil log t\rceil}^{3/4}) . This bound is tight upto a factor of O((log t)^{3/4}). Let (P,\leq) be a partially ordered set and let G_{P} denote its underlying comparability graph. Let dim(P) denote the poset dimension of P. Another interesting consequence of our result is to show that dim(P) \leq 2(k+2) \lceil 2e \log n \rceil, where k denotes the degeneracy of G_{P}. Also, we get a deterministic algorithm that runs in O(n^2k) time to construct a 16k(\lceil 2.42 log n\rceil + 1) sized realizer for P. As far as we know, though very good upper bounds exist for poset dimension in terms of maximum degree of its underlying comparability graph, no upper bounds in terms of the degeneracy of the underlying comparability graph is seen in the literature.