In 2003, the frequency assignment problem in a cellular network motivated Even et al. to introduce a new coloring problem: Conflict-Free coloring. Inspired by this problem and by the Gardner-Bodlaender’s coloring game, in 2020, Chimelli and Dantas introduced the Conflict-Free Closed Neighborhood \(k\)-coloring game (CFCN \(k\)-coloring game). The game starts with an uncolored graph \(G\), \(k\geq 2\) different colors, and two players, Alice and Bob, who alternately color the vertices of \(G\). Both players can start the game and respect the following legal coloring rule: for every vertex \(v\), if the closed neighborhood \(N[v]\) of \(v\) is fully colored then there exists a color that was used only once in \(N[v]\). Alice wins if she ends up with a Conflict-Free Closed Neighborhood \(k\)-coloring of \(G\), otherwise, Bob wins if he prevents it from happening. In this paper, we introduce the game for open neighborhoods, the Conflict-Free Open Neighborhood \(k\)-coloring game (CFON \(k\)-coloring game), and study both games on graph classes determining the least number of colors needed for Alice to win the game.

This paper investigates the number of rooted biloopless nonseparable planar near-triangulations and presents some formulae for such maps with three parameters: the valency of root-face, the number of edges and the number of inner faces. All of them are almost summation-free.

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, we confirm the total-coloring conjecture for 1-planar graphs without 4-cycles with maximum degree \(\Delta\geq10\).

For a graph \(G=(V,E)\) of size \(q\), a bijection \(f : E \to \{1,2,\ldots,q\}\) is a local antimagic labeling if it induces a vertex labeling \(f^+ : V \to \mathbb{N}\) such that \(f^+(u) \ne f^+(v)\), where \(f^+(u)\) is the sum of all the incident edge label(s) of \(u\), for every edge \(uv \in E(G)\). In this paper, we make use of matrices of fixed sizes to construct several families of infinitely many tripartite graphs with local antimagic chromatic number 3.

An outer independent double Roman dominating function (OIDRDF) of a graph \( G \) is a function \( f:V(G)\rightarrow\{0,1,2,3\} \) satisfying the following conditions:
(i) every vertex \( v \) with \( f(v)=0 \) is adjacent to a vertex assigned 3 or at least two vertices assigned 2;
(ii) every vertex \( v \) with \( f(v)=1 \) has a neighbor assigned 2 or 3;
(iii) no two vertices assigned 0 are adjacent.
The weight of an OIDRDF is the sum of its function values over all vertices, and the outer independent double Roman domination number \( \gamma_{oidR}(G) \) is the minimum weight of an OIDRDF on \( G \). Ahangar et al. [Appl. Math. Comput. 364 (2020) 124617] established that for every tree \( T \) of order \( n \geq 4 \), \( \gamma_{oidR}(T)\leq\frac{5}{4}n \) and posed the question of whether this bound holds for all connected graphs. In this paper, we show that for a unicyclic graph \( G \) of order \( n \), \( \gamma_{oidR}(G) \leq \frac{5n+2}{4} \), and for a bicyclic graph, \( \gamma_{oidR}(G) \leq \frac{5n+4}{4} \). We further characterize the graphs attaining these bounds, providing a negative answer to the question posed by Ahangar et al.

Let \(G\) be a \((p,q)\) graph. Let \(f\) be a function from \(V(G)\) to the set \(\{1,2,\ldots, k\}\) where \(k\) is an integer \(2< k\leq \left|V(G)\right|\). For each edge \(uv\) assign the label \(r\) where \(r\) is the remainder when \(f(u)\) is divided by \(f(v)\) (or) \(f(v)\) is divided by \(f(u)\) according as \(f(u)\geq f(v)\) or \(f(v)\geq f(u)\). \(f\) is called a \(k\)-remainder cordial labeling of \(G\) if \(\left|v_{f}(i)-v_{f}(j)\right|\leq 1\), \(i,j\in \{1,\ldots , k\}\) where \(v_{f}(x)\) denote the number of vertices labeled with \(x\) and \(\left|\eta_{e}(0)-\eta_{o}(1)\right|\leq 1\) where \(\eta_{e}(0)\) and \(\eta_{o}(1)\) respectively denote the number of edges labeled with even integers and number of edges labeled with odd integers. A graph with admits a \(k\)-remainder cordial labeling is called a \(k\)-remainder cordial graph. In this paper we investigate the \(4\)-remainder cordial labeling behavior of Prism, Crossed prism graph, Web graph, Triangular snake, \(L_{n} \odot mK_{1}\), Durer graph, Dragon graph.

Given a connected graph \(H\), its first Zagreb index \(M_{1}(H)\) is equal to the sum of squares of the degrees of all vertices in \(H\). In this paper, we give a best possible lower bound on \(M_{1}(H)\) that guarantees \(H\) is \(\tau\)-path-coverable and \(\tau\)-edge-Hamiltonian, respectively. Our research supplies a continuation of the results presented by Feng et al. (2017).

The degree of an edge \(uv\) of a graph \(G\) is \(d_G(u)+d_G(v)-2.\) The degree associated edge reconstruction number of a graph \(G\) (or dern(G)) is the minimum number of degree associated edge-deleted subgraphs that uniquely determines \(G.\) Graphs whose vertices all have one of two possible degrees \(d\) and \(d+1\) are called \((d,d+1)\)-bidegreed graphs. It was proved, in a sequence of two papers [1,17], that \(dern(mK_{1,3})=4\) for \(m>1,\) \(dern(mK_{2,3})=dern(rP_3)=3\) for \(m>0, ~r>1\) and \(dern(G)=1\) or \(2\) for all other bidegreed graphs \(G\) except the \((d,d+1)\)-bidegreed graphs in which a vertex of degree \(d+1\) is adjacent to at least two vertices of degree \(d.\) In this paper, we prove that \(dern(G)= 1\) or \(2\) for this exceptional bidegreed graphs \(G.\) Thus, \(dern(G)\leq 4\) for all bidegreed graphs \(G.\)

A proper total coloring of a graph \( G \) such that there are at least 4 colors on those vertices and edges incident with a cycle of \( G \), is called an acyclic total coloring. The acyclic total chromatic number of \( G \), denoted by \( \chi^{”}_{a}(G) \), is the smallest number of colors such that \( G \) has an acyclic total coloring. In this article, we prove that for any graph \( G \) with \( \Delta(G)=\Delta \) which satisfies \( \chi^{”}(G)\leq A \) for some constant \( A \), and for any integer \( r \), \( 1\leq r \leq 2\Delta \), there exists a constant \( c>0 \) such that if \( g(G)\geq\frac{c\Delta}{r}\log\frac{\Delta^{2}}{r} \), then \( \chi^{”}_{a}(G)\leq A+r \).

We study a discrete-time model for the spread of information in a graph, motivated by the idea that people believe a story when they learn of it from two different origins. Similar to the burning number, in this problem, information spreads in rounds and a new source can appear in each round. For a graph \(G\), we are interested in \(b_2(G)\), the minimum number of rounds until the information has spread to all vertices of graph \(G\). We are also interested in finding \(t_2(G)\), the minimum number of sources necessary so that the information spreads to all vertices of \(G\) in \(b_2(G)\) rounds. In addition to general results, we find \(b_2(G)\) and \(t_2(G)\) for the classes of spiders and wheels and show that their behavior differs with respect to these two parameters. We also provide examples and prove upper bounds for these parameters for Cartesian products of graphs.