Let \(G\) be a loopless connected graph. A graph \(G\) is reduced if it contains no collapsible subgraph. Catlin (posted by Chen and Lai [9]) conjectured that every connected reduced graph is either 2-colorable or 3-colorable. A weaker conjecture states that the independence number of a connected reduced graph \(G\) is at least one-third of its number of vertices. In this paper, we establish a lower bound on the independence number in reduced graphs. As an application, we examine the independence number conjecture for reduced graphs with a given upper bound on the number of vertices. Also, we investigate the chromatic number of reduced planar graphs under given conditions.

Graph pebbling is a network optimization method modeling the movement of resources in transit. A pebbling move on a connected graph \(G\) removes two pebbles from a vertex, places one on an adjacent vertex, and discards the other, with the loss analogous to packet loss in communication networks. The generalized version, \(t\)-pebbling, defines the \(t\)-pebbling number \(f_t(G)\) as the smallest integer such that, from any distribution of \(f_t(G)\) pebbles, \(t\) pebbles can be moved to any vertex \(v\) via a pebbling sequence. A graph satisfies the \(2t\)-pebbling property if \(2t\) pebbles can be transferred to \(v\) when \(2f_t(G)-q+1\) pebbles are distributed, where \(q\) is the number of occupied vertices. This paper establishes a lower bound for the rooted product of two graphs \(G\) and \(H\), sharp when one factor is a path, complete graph, or star. Further results on pebbling in triangle-free graphs are also obtained, including verification of the \(2t\)-pebbling property for rooted products involving such graphs.

It is known that null graphs are the only (regular) graphs with local antimagic chromatic 1 and 1-regular graphs are the only regular graphs without local antimagic chromatic number. In this paper, we first use matrices of size \((2m+1) \times (2k+1)\) to completely determine the local antimagic chromatic number of the join of null graphs \(O_m\) and 1-regular graphs \((2k+1)P_2\) for all \(k\ge 1, m\ge 2\). We then make use of other matrices of same size to obtain the local antimagic chromatic number of another family of tripartite graphs. Consequently, we obtained infinitely many (possibly disconnected) regular tripartite graphs with local antimagic chromatic number 3.

Let \(2\le k\in\mathbb{Z}\). We say that a total coloring of a \(k\)-regular simple graph via \(k+1\) colors is an efficient total coloring if each color yields an efficient dominating set, where the efficient domination condition applies to the restriction of each color class to the vertex set. We prove that Hamming shells of star transposition graphs and Hamming cubes have efficient total colorings. Also in this work, a focus is set upon the graphs of girths \(2k\) and \(k\). Efficient total colorings of finite connected simple cubic graphs of girth 6 are constructed. These are of two specific types, namely: (a) those whose 6-cycles use just 3 colors with antipodal monochromatic pairs of vertices or edges; (b) those whose 6-cycles do not respect item (a) so they use four colors. An orthogonality property holds for all graphs of type (a). Such orthogonality property allows further edge-half-girth colorings in the corresponding prism graphs.

Graph Theory was started by Euler after solving the famous Konigsberg bridge problem. The Graph Coloring is among one of the famous topic for research since it has many beautiful theorems on optimization and its applications in numerous fields of science. The Pi coloring is the coloring of graph parts without a recurring pattern. As a result, it is defined as a function from a set of graph elements with similar properties to the power set of colors, so that each set receives a different color set from the power set. In consequence, Incident Vertex Pi coloring of a graph is defined as the coloring of incident vertices for every single edge with Pi coloring. Incident Vertex Pi coloring of the complete graph is \(n\), wheel graph, star graph and double star graph is \(n+1\), diamond, friendship graphs is \(\Delta +1\), and double fan graph is \(\Delta +2\). In this research, we derived the Incident Vertex PI coloring of Star and Double Star graph’s Middle graph, Total graph, Line graph, and Splitting graph.

For a graph \(G\) with a (not necessarily proper) vertex coloring, a set \(D\subseteq V(G)\) is a polychromatic dominating set of \(G\) if it is a dominating set and each vertex in \(D\) is a different color. The polychromatic domination number of \(G\), \(\rho(G)\), is the minimum number of colors such that, for any \(\rho(G)\)-coloring (with exactly \(\rho(G)\) colors) of the vertices of \(G\), there exists a polychromatic dominating set of \(G\). This paper begins the exploration of the polychromatic domination number. In particular we give tight upper and lower bounds for \(\rho(G)\) both of which are functions of the minimum degree of \(G\).

A novel approach to building strong starters in cyclic groups of orders \(n\) divisible by 3 from starters of smaller orders is presented. A strong starter in \(\mathbb{Z}_n\) (\(n\) odd) is a partition of the set \(\{1,2,\dots,n-1\}\) into pairs \(\{a_i,b_i\}\) such that all pair sums \(a_i+b_i\) are distinct and nonzero modulo \(n\) and all differences \(\pm(a_i-b_i)\) are distinct and nonzero modulo \(n\). A special interest to strong starters of odd orders divisible by 3 is motivated by Horton’s conjecture, which claims that such starters exist (except when \(n=3\) or \(9\)) but remains unproven since 1989. We begin with a starter of order \(p\) coprime with 3 and describe an algorithm to obtain a Sudoku-type problem modulo 3 whose solution, if exists, yields a strong starter of order \(3p\). The process leading from the original to the final starter is called triplication. Besides theoretical aspects of the construction, practicality of this approach is demonstrated. A general-purpose constraint-satisfaction (SAT) solver z3 is used to solve the Sudoku-type problem; various performance statistics are presented.

Let P_n + 1, C_n and S_n represent a path, cycle, and star with n edges, Q_n denote the n-dimensional hypercube graph. The (ℋ₁, ℋ₂)−multidecomposition of G for graphs ℋ₁, ℋ₂, and G is a decomposition of G into copies of ℋ₁ and ℋ₂, where there is at least one copy of ℋ₁ and at least one copy of ℋ₂. In this paper, we prove that the graph Q_n is (S_n − 2, C₄)−multidecomposable for n ≥ 4 and (S_n − 4, P₅)−multidecomposable for n ≥ 5.