Search

AbstractIn 2021, we introduced one type of the generalization of dominator coloring via packing coloring and distance domination. In this paper, we present a second type of such generalization, namely distance dominator packing coloring of type II, defined as follows. A coloring c is a k-distance dominator packing coloring of type II of G if it is a k-packing coloring of G and for each u ∈ V (G) there exists i ∈ {1, 2, 3, . . . , k} such that u c(u)-distance dominates each vertex from the color class of color i (i.e., the distance between u and all vertices from color class of color i is at most c(u)). The smallest integer k such that there exists a k-distance dominator packing coloring of G is the distance dominator packing chromatic number of type II of G, denoted by . In this paper, we provide some lower and upper bounds on the distance dominator packing chromatic number of type II, characterize connected graphs G with , and consider the relation between the packing coloring, distance dominator packing coloring of type I (introduced by Ferme and Mesarič Štesl in 2021) and distance dominator packing coloring of type II for a given graph. [ABSTRACT FROM AUTHOR]

The DP-coloring is a generalization of the list coloring, introduced by Dvořák and Postle. Let H = (L , H) be a cover of a graph G and P DP (G , H) be the number of H -colorings of G. The DP color function P DP (G , m) of G, introduced by Kaul and Mudrock, is the minimum value of P DP (G , H) where the minimum is taken over all possible m-fold covers H of G. For the family of n-vertex connected graphs, one can deduce that trees maximize the DP color function, from two results of Kaul and Mudrock. In this paper we obtain tight upper bounds for the DP color function of n-vertex 2-connected graphs. Another concern in this paper is the canonical labeling in a cover. It is well known that if an m-fold cover H of a graph G has a canonical labeling, then P DP (G , H) = P (G , m) in which P(G, m) is the chromatic polynomial of G. However the converse statement of this conclusion is not always true. We give examples that for some m and G, there exists an m-fold cover H of G such that P DP (G , H) = P (G , m) , but H has no canonical labelings. We also prove that when G is a unicyclic graph or a theta graph, for each m ≥ 3 , if P DP (G , H) = P (G , m) , then H has a canonical labeling. [ABSTRACT FROM AUTHOR]

AbstractLet c: V(G) → {1, . . . , ℓ} = [ℓ] be a proper vertex coloring of G and C(i) = {u ∈ V(G): c(u) = i} for i ∈ [ℓ]. The k-color code rk(v|c) of vertex v is the ordered ℓ-tuple (aG(v,C(1)), . . . , aG(v,C(ℓ))) whereIf every two vertices have different color codes, then c is a (k, ℓ)-locating coloring of G. The k-locating chromatic number of graph G, denoted by , is the smallest integer ℓ such that G has a (k, ℓ)-locating coloring. In this paper, we propose this concept as an extension of diam(G)-locating chromatic number and 2-locating chromatic number which are known as the locating chromatic number, denoted χL(G), and neighbor-locating chromatic number, denoted , respectively. In this paper, we give sharp bounds for and where G◦H and are the corona and edge corona of G and H, respectively. We formulate an integer linear programming model to determine , noting that almost all graphs have diameter 2 and for every graph G of diameter 2. [ABSTRACT FROM AUTHOR]

Let C k (n) denote the family of all connected graphs of order n with chromatic number k. In this paper we show that the conjecture proposed by Tomescu which if x ≥ k ≥ 4 and G ∈ C k (n) , then P (G , x) ≤ (x) k (x - 1) n - k holds under the additional condition that G has an independent cut-set T of size at most 2 such that the number of components in G \ T is equal to the independence number of G. [ABSTRACT FROM AUTHOR]

The vertex arboricity a(G) of a graph G is the minimum number of colors required to color the vertices of G such that no cycle is monochromatic. A graph G is 1-planar if it can be drawn in the plane so that each edge has at most one crossing. In this paper, we proved that every 1-planar graph without 5-cycles has minimum degree at most 5; Every 1-planar graph of girth at least 7 has minimum degree at most 3. The following conclusions can be obtained by combining the existing conclusions and our proofs: if G is a 1-planar graph without 5-cycles, then a (G) ≤ 3 ; if G is a 1-planar graph with g (G) ≥ 7 , then a (G) ≤ 2 . [ABSTRACT FROM AUTHOR]

An equitable k-partition ( k ≥ 2 ) of a vertex set S is a partition of S into k subsets (may be empty sets) such that the sizes of any two subsets of S differ by at most one. A local-equitable k-coloring ( k ≥ 2 ) of G is an assignment of k colors to the vertices of G such that, for every maximal clique H of G, the coloring on H forms an equitable k-partition of H. Local-equitable coloring of graphs is a generalization of the proper vertex coloring of graphs and also a stronger version of clique-coloring of graphs. Claw-free graphs with maximum degree four are proved to be 2-clique-colorable [Discrete Math. Theoret. Comput. Sci. 11 (2) (2009), 15–24] but not necessary local-equitably 2-colorable. In this paper, given a claw-free graph G with maximum degree at most four, we present a linear time algorithm to give a local-equitable 2-coloring of G or decide that G is not local-equitably 2-colorable. As a corollary, we get that claw-free perfect graphs with maximum degree at most four are local-equitably 2-colorable. [ABSTRACT FROM AUTHOR]

This paper is motivated by the problem of determining the related chromatic numbers of some hypergraphs. A hypergraph Π q (n , k) is defined from a projective space PG (n - 1 , q) , where the vertices are points and the hyperedges are (k - 1) -dimensional subspaces. For the perfect balanced rainbow-free colorings, we show that χ ¯ p (Π q (n , k)) = q n - 1 l (q - 1) , where k ≥ ⌈ n + 1 2 ⌉ and l is the smallest nontrivial factor of q n - 1 q - 1 . For the complete colorings, we prove that there is no complete coloring for Π q (n , k) with 2 ≤ k < n . We also provide some results on the related chromatic numbers of subhypergraphs of Π q (n , k) . [ABSTRACT FROM AUTHOR]

A 1-removed subgraph G f of a graph G = (V , E) is obtained by (i) selecting at most one edge f(v) for each vertex v ∈ V , such that v ∈ f (v) ∈ E (the mapping f : V → E ∪ { ∅ } is allowed to be non-injective), and (ii) deleting all the selected edges f(v) from the edge set E of G. Proper vertex colorings of 1-removed subgraphs proved to be a useful tool for earlier research on some Turán-type problems. In this paper, we introduce a systematic investigation of the graph invariant 1-robust chromatic number, denoted as χ 1 (G) . This invariant is defined as the minimum chromatic number χ (G f) among all 1-removed subgraphs G f of G. We also examine other standard graph invariants in a similar manner. [ABSTRACT FROM AUTHOR]

Let G, H be two non-empty graphs and k be a positive integer. The Gallai-Ramsey number gr k (G : H) is defined as the minimum positive integer N such that for all n ≥ N , every k-edge-coloring of K n contains either a rainbow subgraph G or a monochromatic subgraph H. The Gallai-Ramsey multiplicity GM k (G : H) is defined as the minimum total number of rainbow subgraphs G and monochromatic subgraphs H for all k-edge-colored K gr k (G : H) . In this paper, we get some exact values of the Gallai-Ramsey multiplicity for rainbow small trees versus general monochromatic graphs under a sufficiently large number of colors. We also study the bipartite Gallai-Ramsey multiplicity. [ABSTRACT FROM AUTHOR]

Given two graphs G and H, the generalk-colored Gallai–Ramsey number gr k (G : H) is defined to be the minimum integer m such that every k-coloring of the complete graph on m vertices contains either a rainbow copy of G or a monochromatic copy of H. Interesting problems arise when one asks how many such rainbow copy of G and monochromatic copy of H must occur. The Gallai–Ramsey multiplicity GM k (G : H) is defined as the minimum total number of rainbow copy of G and monochromatic copy of H in any exact k-coloring of K gr k (G : H) . In this paper, we give upper and lower bounds for Gallai–Ramsey multiplicity involving some small rainbow subgraphs. [ABSTRACT FROM AUTHOR]

Let G be a graph. A bisection of G is a bipartition of V(G) with V (G) = V 1 ∪ V 2 , V 1 ∩ V 2 = ∅ and | | V 1 | - | V 2 | | ≤ 1 . Bollobás and Scott conjectured that every graph admits a bisection such that for every vertex, its external degree is greater than or equal to its internal degree minus one. In this paper, we confirm this conjecture for some regular graphs. Our results extend a result given by Ban and Linial (J Graph Theory 83:5–18, 2016). We also give an upper bound of the maximum bisection of graphs. [ABSTRACT FROM AUTHOR]

The problem of injective coloring in graphs can be revisited through two different approaches: coloring the two-step graphs and vertex partitioning of graphs into open packing sets, each of which is equivalent to the injective coloring problem itself. Taking these facts into account, we observe that the injective coloring lies between graph coloring and domination theory. We make use of these three points of view in this paper so as to investigate the injective coloring of some well-known graph products. We bound the injective chromatic number of direct and lexicographic product graphs from below and above. In particular, we completely determine this parameter for the direct product of two cycles. We also give a closed formula for the corona product of two graphs. [ABSTRACT FROM AUTHOR]

Let G be a nontrivial connected and vertex-colored graph. A vertex subset X is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G - S ; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of (G - x y) - S . For a connected graph G, the rainbow vertex-disconnection number of G, rvd(G), is the minimum number of colors that are needed to make G rainbow vertex-disconnected. In this paper, we prove for any K 4 -minor free graph, r v d (G) ≤ Δ (G) and the bound is sharp. We show it is NP-complete to determine the rainbow vertex-disconnection numbers for bipartite graphs and split graphs. Moreover, we show for every ϵ > 0 , it is impossible to efficiently approximate the rainbow vertex-disconnection number of any bipartite graph and split graph within a factor of n 1 3 - ϵ unless Z P P = N P . [ABSTRACT FROM AUTHOR]

The Borodin–Kostochka Conjecture states that for a graph G, if Δ (G) ≥ 9 , then χ (G) ≤ max { Δ (G) - 1 , ω (G) } . In this paper, we prove the Borodin–Kostochka Conjecture holding for odd-hole-free graphs. [ABSTRACT FROM AUTHOR]

In this paper we study the achromatic arboricity of the complete graph. This parameter arises from the arboricity of a graph as the achromatic index arises from the chromatic index. The achromatic arboricity of a graph G, denoted by A α (G) , is the maximum number of colors that can be used to color the edges of G such that every color class induces a forest but any two color classes contain a cycle. In particular, if G is a complete graph we prove that 1 4 n 3 2 - c 1 n ≤ A α (G) ≤ 1 2 n 3 2 - c 2 n where c 1 and c 2 are constants such that 0 < c 1 , c 2 < 1 2 . [ABSTRACT FROM AUTHOR]

A compatible spanning circuit in an edge-colored graph G (not necessarily properly) is defined as a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. The existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and compatible Euler tours) has been studied extensively. Recently, sufficient conditions for the existence of compatible spanning circuits visiting each vertex at least a specified number of times in specific edge-colored graphs satisfying certain degree conditions have been established. In this paper, we continue the research on sufficient conditions for the existence of such compatible s-panning circuits. We consider edge-colored graphs containing no certain forbidden induced subgraphs. As applications, we also consider the existence of such compatible spanning circuits in edge-colored graphs G with κ(G) ≥ α(G), κ(G) ≥ α(G) − 1 and κ (G) ≥ α(G), respectively. In this context, κ(G), α(G) and κ (G) denote the connectivity, the independence number and the edge connectivity of a graph G, respectively. [ABSTRACT FROM AUTHOR]

The problem of finding the minimum number of colors to color a graph properly without containing any bicolored copy of a fixed family of subgraphs has been widely studied. Most well-known examples are star coloring and acyclic coloring of graphs (Grünbaum in Isreal J Math 14(4):390–498, 1973) where bicolored copies of P 4 and cycles are not allowed, respectively. In this paper, we introduce a variation of these problems and study proper coloring of graphs not containing a bicolored path of a fixed length and provide general bounds for all graphs. A P k -coloring of an undirected graph G is a proper vertex coloring of G such that there is no bicolored copy of P k in G, and the minimum number of colors needed for a P k -coloring of G is called the P k -chromatic number of G, denoted by s k (G). We provide bounds on s k (G) for all graphs, in particular, proving that for any graph G with maximum degree d ≥ 2 , and k ≥ 4 , s k (G) ≤ ⌈ 6 10 d k - 1 k - 2 ⌉. Moreover, we find the exact values for the P k -chromatic number of the products of some cycles and paths for k = 5 , 6. [ABSTRACT FROM AUTHOR]

Tashkinov-trees have been used as a tool for proving bounds on the chromatic index, and are becoming a fundamental tool for edge-coloring. Was its publication in a language different from English an obstacle for the accessibility of a clean and complete proof of Tashkinov’s fundamental theorem? Tashkinov’s original, Russian paper offers a clear presentation of this theorem and its proof. The theorem itself has been well understood and successfully applied, but the proof is more difficult. It builds a truly amazing recursive machine, where the various cases necessitate a refined and polished analysis to fit into one another with surprising smoothness and accuracy. The difficulties were brilliantly unknotted by the author, deserving repeated attention. The present work is the result of reading, translating, reorganizing, rewriting, completing, shortcutting and annotating Tashkinov’s proof. It is essentially the same proof, with non-negligeable communicational differences though, for instance completing it wherever it occurred to be necessary, and simplifying it whenever it appeared to be possible, at the same time trying to adapt it to the habits and taste of the international graph theory community. [ABSTRACT FROM AUTHOR]

An odd hole is an induced odd cycle of length at least five. Let ℓ ≥ 2 be an integer, and let G ℓ denote the family of graphs which have girth 2 ℓ + 1 and have no holes of odd length at least 2 ℓ + 5 . In this paper, we prove that every graph G ∈ ∪ ℓ ≥ 3 G ℓ is 4-colourable. [ABSTRACT FROM AUTHOR]

DP-coloring was introduced by Dvořák and Postle as a generalization of list coloring and signed coloring. A new coloring, strictly f-degenerate transversal, is a further generalization of DP-coloring and L-forested-coloring. In this paper, we present some structural results on planar and toroidal graphs with forbidden configurations, and establish some sufficient conditions for the existence of strictly f-degenerate transversal based on these structural results. Consequently, (i) every toroidal graph without subgraphs in Fig. 2 is DP-4-colorable, and has list vertex arboricity at most 2, (ii) every toroidal graph without 4-cycles is DP-4-colorable, and has list vertex arboricity at most 2, (iii) every planar graph without subgraphs isomorphic to the configurations in Fig. 3 is DP-4-colorable, and has list vertex arboricity at most 2. These results improve upon previous results on DP-4-coloring (Kim and Ozeki in Discrete Math 341(7):1983–1986. , 2018; Sittitrai and Nakprasit in Bull Malays Math Sci Soc 43(3):2271–2285. , 2020) and (list) vertex arboricity (Choi and Zhang in Discrete Math 333:101–105. , 2014; Huang et al. in Int J Math Stat 16(1):97–105, 2015; Zhang in Iranian Math Soc 42(5):1293–1303, 2016). [ABSTRACT FROM AUTHOR]

An edge-colored graph is called rainbow if every two edges receive distinct colors, and called proper if every two adjacent edges receive distinct colors. An edge-colored graph G c is properly vertex/edge-pancyclic if every vertex/edge of the graph is contained in a proper cycle of length k for every k with 3 ≤ k ≤ | V (G) | . A triangle C of G c is called a 2-triangle if C receives exactly two colors. We call G c 2-triangle-free if G c contains no 2-triangle. Let d c (v) be the number of colors on the edges incident to v in G c and let δ c (G) be the minimum d c (v) over all the vertices v ∈ V (G c) . We show in this paper that: (i) a 2-triangle-free edge-colored complete graph K n c is properly vertex-pancyclic if δ c (K n) ≥ ⌈ n 3 ⌉ + 1 , and is properly edge-pancyclic if δ c (K n) ≥ ⌈ n 3 ⌉ + 2 . (ii) with the exception of a few edge-colored graphs on at most 9 vertices, every vertex of a 2-triangle-free edge-colored complete graph K n c with δ c (K n) ≥ 4 is contained in a rainbow C 4 ; (iii) every vertex of a 2-triangle-free edge-colored complete graph K n c with δ c (K n) ≥ 5 is contained in a rainbow C 5 unless G is proper or G is a special edge-colored K 8 . [ABSTRACT FROM AUTHOR]

A proper vertex coloring of a graph G is acyclic if there is no bicolored cycles in G. A graph G is acyclically k-choosable if for any list assignment L = {L(v): v ∈ V(G)} with ∣L(v)∣ ≥ k for each vertex v ∈ V(G), there exists an acyclic proper vertex coloring ϕ of G such that ϕ(v) ∈ L(v) for each vertex v ∈ V(G). In this paper, we prove that every graph G embedded on the surface with Euler characteristic number ε = −1 is acyclically 11-choosable. [ABSTRACT FROM AUTHOR]

A strong edge-coloring of a graph G = (V , E) is a partition of its edge set E into induced matchings. In this paper, we will study the list version of strong edge-colorings of several classes of sparse graphs, including bipartite graphs and graphs with small edge weight, where the edge weight of a graph is defined by max { d G (u) + d G (v) | u v ∈ E (G) } . We show that: (1) if G is a bipartite graph with bipartition (A, B) such that Δ (A) = 2 and Δ (B) = Δ ≥ 4 , then G has strong list-chromatic index at most 3 Δ - 3 ; (2) every graph with edge weight at most 5 (resp. 6) has strong list-chromatic index at most 7 (resp. 11) and every planar graph with edge weight at most 6 has strong list-chromatic index at most 10; and (3) every graph with edge weight at most 7 has strong list-chromatic index at most 16. [ABSTRACT FROM AUTHOR]

Let G and H be two vertex disjoint graphs. The union G ∪ H is the graph with V (G ∪ H) = V (G) ∪ (H) and E (G ∪ H) = E (G) ∪ E (H) . The join G + H is the graph with V (G + H) = V (G) ∪ V (H) and E (G + H) = E (G) ∪ E (H) ∪ { x y | x ∈ V (G) , y ∈ V (H) } . We use P k to denote a path on k vertices, use fork to denote the graph obtained from K 1 , 3 by subdividing an edge once, and use crown to denote the graph K 1 + K 1 , 3 . In this paper, we show that (i) χ (G) ≤ 3 2 (ω 2 (G) - ω (G)) if G is (crown, P 5 )-free, (ii) χ (G) ≤ 1 2 (ω 2 (G) + ω (G)) if G is (crown, fork)-free, and (iii) χ (G) ≤ 1 2 ω 2 (G) + 3 2 ω (G) + 1 if G is (crown, P 3 ∪ P 2 )-free. [ABSTRACT FROM AUTHOR]

The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. Akiyama, Exoo and Harary conjectured that ⌈ Δ 2 ⌉ ≤ l a (G) ≤ ⌈ Δ + 1 2 ⌉ for any graph G with maximum degree Δ , and proved the conjecture holds for forests. This conjecture has been verified for certain graph families with treewidth at most 3. In the paper we improve these former results by validating the conjecture for all graphs with treewidth at most 4. [ABSTRACT FROM AUTHOR]

This paper explores a new direction in the well studied area of graph saturation—we introduce the notion of rainbow saturation. A graph G is rainbow H-saturated if there is some proper edge coloring of G which is rainbow H-free (that is, it has no copy of H whose edges are all colored distinctly), but where the addition of any edge makes such a rainbow H-free coloring impossible. Taking the maximum number of edges in a rainbow H-saturated graph recovers the rainbow Turán numbers whose systematic study was begun by Keevash, Mubayi, Sudakov, and Verstraëte. In this paper, we initiate the study of corresponding rainbow saturation number—the minimum number of edges among all rainbow H-saturated graphs. We give examples of graphs for which the rainbow saturation number is bounded away from the traditional saturation number (including all complete graphs K n for n ≥ 4 and several bipartite graphs). It is notable that there are non-bipartite graphs for which this is the case, as this does not happen when it comes to the rainbow Turán number versus the traditional Turán number. We also show that saturation numbers are at most linear for a large class of graphs, providing a partial rainbow analogue of a well known theorem of Kászonyi and Tuza. We conclude this paper with a number of related open questions and conjectures. [ABSTRACT FROM AUTHOR]

Inspired by the fundamental work of Lechuga and Murillo (Topology 39:89–94, 2000) who established a connection between graph theory and rational homotopy theory, this paper defines new algebraic invariants for a non-oriented, simple, connected and finite graph G namely the rational cohomology H ∗ (G) , the Lusternik-Schnirelmann category cat(G), the cohomology Euler-Poincaré characteristic χ G , the Koszul-Poincare series U G (z) and the formal dimension fd(G). Moreover we compute those invariants by exploiting some deep well known theorems from rational homotopy theory. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a weak DP-partitioning which combines the concepts of DP-coloring and vertex-partition. Let G be a planar graph without 4- and 6-cycles. We show that G is weakly DP- (F 2 , F) -colorable. The result implies that G has a partition of the vertex set into two sets, where one set induces a forest, and the other induces a linear forest as shown by Huang et al. We also prove that G is weakly DP- (F 2 , F 0 , F 0) -colorable which improves the result by Fang and Wang that G is weakly DP- (F 2 , F 2 , F 0) -colorable. [ABSTRACT FROM AUTHOR]

Let F t (n) denote the family of all connected graphs of order n with clique number t. In this paper, we present a new upper bound for the chromatic polynomial of a graph G in F t (n) in terms of the clique number of G. Moreover, we also show that the conjecture proposed by Tomescu, which says that if x ≥ k ≥ 4 and G is a connected graph on n vertices with chromatic number k, then P (G , x) ≤ (x) k (x - 1) n - k holds under certain conditions, where (x) k = x (x - 1) ⋯ (x - k + 1) , such as the clique number ω (G) = k ≥ 4 , ω (G) = k - 1 (k ≥ 7) with two (k - 1) -cliques having at most k - 3 vertices in common, or maximum degree ▵ (G) = n - 2 . [ABSTRACT FROM AUTHOR]

Given two non-empty graphs G, H and a positive integer k, the Gallai–Ramsey number gr k (G : H) is defined as the minimum integer N such that for all n ≥ N , every k-edge-coloring of K n contains either a rainbow colored copy of G or a monochromatic copy of H. In this paper, we got some exact values or bounds for gr k (P 5 : H) (k ≥ 3) if H is a general graph or a star with extra independent edges or a pineapple. [ABSTRACT FROM AUTHOR]

Let F 1 and F 2 be two disjoint graphs. The union F 1 ∪ F 2 is a graph with vertex set V (F 1) ∪ V (F 2) and edge set E (F 1) ∪ E (F 2) , and the join F 1 + F 2 is a graph with vertex set V (F 1) ∪ V (F 2) and edge set E (F 1) ∪ E (F 2) ∪ { x y | x ∈ V (F 1) and y ∈ V (F 2) } . In this paper, we present a characterization to (P 5 , K 1 ∪ K 3) -free graphs, prove that χ (G) ≤ 2 ω (G) - 1 if G is (P 5 , K 1 ∪ K 3) -free. Based on this result, we further prove that χ (G) ≤ max { 2 ω (G) , 15 } if G is a (P 5 , K 1 + (K 1 ∪ K 3)) -free graph. We also construct a (P 5 , K 1 + (K 1 ∪ K 3)) -free graph G with χ (G) = 2 ω (G) . [ABSTRACT FROM AUTHOR]

Let F t (n) denote the family of all connected graphs of order n with clique number t. In this paper, we present a new upper bound for the chromatic polynomial of a graph G in F t (n) in terms of the clique number of G. Moreover, we also show that the conjecture proposed by Tomescu, which says that if x ≥ k ≥ 4 and G is a connected graph on n vertices with chromatic number k, then P (G , x) ≤ (x) k (x - 1) n - k holds under certain conditions, where (x) k = x (x - 1) ⋯ (x - k + 1) , such as the clique number ω (G) = k ≥ 4 , ω (G) = k - 1 (k ≥ 7) with two (k - 1) -cliques having at most k - 3 vertices in common, or maximum degree ▵ (G) = n - 2 . [ABSTRACT FROM AUTHOR]

Given two non-empty graphs G, H and a positive integer k, the Gallai–Ramsey number gr k (G : H) is defined as the minimum integer N such that for all n ≥ N , every k-edge-coloring of K n contains either a rainbow colored copy of G or a monochromatic copy of H. In this paper, we got some exact values or bounds for gr k (P 5 : H) (k ≥ 3) if H is a general graph or a star with extra independent edges or a pineapple. [ABSTRACT FROM AUTHOR]

Let F 1 and F 2 be two disjoint graphs. The union F 1 ∪ F 2 is a graph with vertex set V (F 1) ∪ V (F 2) and edge set E (F 1) ∪ E (F 2) , and the join F 1 + F 2 is a graph with vertex set V (F 1) ∪ V (F 2) and edge set E (F 1) ∪ E (F 2) ∪ { x y | x ∈ V (F 1) and y ∈ V (F 2) } . In this paper, we present a characterization to (P 5 , K 1 ∪ K 3) -free graphs, prove that χ (G) ≤ 2 ω (G) - 1 if G is (P 5 , K 1 ∪ K 3) -free. Based on this result, we further prove that χ (G) ≤ max { 2 ω (G) , 15 } if G is a (P 5 , K 1 + (K 1 ∪ K 3)) -free graph. We also construct a (P 5 , K 1 + (K 1 ∪ K 3)) -free graph G with χ (G) = 2 ω (G) . [ABSTRACT FROM AUTHOR]

A Steinberg-type conjecture on circular coloring is recently proposed that for any prime p ≥ 5, every planar graph of girth p without cycles of length from p + 1 to p(p − 2) is Cp-colorable (that is, it admits a homomorphism to the odd cycle Cp). The assumption of p ≥ 5 being prime number is necessary, and this conjecture implies a special case of Jaeger's Conjecture that every planar graph of girth 2p — 2 is Cp-colorable for prime p ≥ 5. In this paper, combining our previous results, we show the fractional coloring version of this conjecture is true. Particularly, the p = 5 case of our fractional coloring result shows that every planar graph of girth 5 without cycles of length from 6 to 15 admits a homomorphism to the Petersen graph. [ABSTRACT FROM AUTHOR]

A domatic (resp. total domatic) k-coloring of a graph G is an assignment of k colors to the vertices of G such that each vertex contains vertices of all k colors in its closed neighborhood (resp. open neighborhood). The domatic (resp. total domatic) number of G, denoted d(G) (resp. d t (G) ), is the maximum k for which G has a domatic (resp. total domatic) k-coloring. In this paper, we show that for two non-trivial graphs G and H, the domatic and total domatic numbers of their Cartesian product G □ H is bounded above by max { | V (G) | , | V (H) | } and below by max { d (G) , d (H) } . Both these bounds are tight for an infinite family of graphs. Further, we show that if H is bipartite, then d t (G □ H) is bounded below by 2 min { d t (G) , d t (H) } and d (G □ H) is bounded below by 2 min { d (G) , d t (H) } . As a consequences, we get new bounds for the domatic and total domatic number of hypercubes and Hamming graphs of certain dimensions, and exact values for some n-dimensional tori which turns out to be a generalization of a result due to Gravier from 2002. [ABSTRACT FROM AUTHOR]

All graph in this paper is connected and simple graph. Let d(u, v) be a distance between any vertex u and v in graph G = (V, E). A function l : V(G) → {1, 2,..., k} is called vertex irregular k-labelling and w : V(G) → N where w(u) = ΣvϵN(u)l(v). If for every uv ϵ E(G), w(u) ≠ w(v) and opt(l) = min(max(li); li vertex irregular labelling) is called a local irregularity vertex coloring. The minimum cardinality of the largest label over all such local irregularity vertex coloring is called chromatic number local irregular, denoted by χlis(G). In this paper, we study about local irregularity vertex coloring of families graphs, namely triangular book graph, square book graph, pan graph, subdivision of pan graph, and grid graphs. [ABSTRACT FROM AUTHOR]

Suppose that G is a graph and ϕ is a proper edge-coloring of G. For a vertex v ∈ V (G) , let C ϕ (v) denote the set of colors assigned to the edges incident with v. The graph G is local neighbor-distinguishing with respect to the coloring ϕ if for any two adjacent vertices x and y of degree at least two, it holds that C ϕ (x) ⊈ C ϕ (y) and C ϕ (y) ⊈ C ϕ (x) . The local neighbor-distinguishing index, denoted χ lnd ′ (G) , of G is defined as the minimum number of colors in a local neighbor-distinguishing edge-coloring of G. For n ≥ 2 , let H n denote the graph obtained from the bipartite graph K 2 , n by inserting a 2-vertex into one edge. In this paper, we show the following results: (1) For any graph G, χ lnd ′ (G) ≤ 3 Δ - 1 ; (2) suppose that G is a planar graph. Then χ lnd ′ (G) ≤ ⌈ 2.8 Δ ⌉ + 4 ; and moreover χ lnd ′ (G) ≤ 2 Δ + 10 if G contains no 4-cycles; χ lnd ′ (G) ≤ Δ + 23 if G is 3-connected; and χ lnd ′ (G) ≤ Δ + 6 if G is Hamiltonian. [ABSTRACT FROM AUTHOR]

A 1-factorization F of a complete graph K 2 n is said to be G-regular, or regular under G, if G is an automorphism group of F acting sharply transitively on the vertex-set. The problem of determining which groups can realize such a situation dates back to a result by Hartman and Rosa (Eur J Comb 6:45–48, 1985) on cyclic groups and it is still open when n is even, although several classes of groups were tested in the recent past. It has been recently proved, see Rinaldi (Australas J Comb 80(2):178–196, 2021) and Mazzuoccolo et al. (Discret Math 342(4):1006–1016, 2019), that a G-regular 1-factorization, together with a complete set of rainbow spanning trees, exists for each group G of order 2n, n odd. The existence for each even n > 2 was proved when either G is cyclic and n is not a power of 2, or when G is a dihedral group. Explicit constructions were given in all these cases. In this paper we extend this result and give explicit constructions when n > 2 is even and G is either abelian but not cyclic, dicyclic, or a non cyclic 2-group with a cyclic subgroup of index 2. [ABSTRACT FROM AUTHOR]

Let G = (V (G) , E (G)) be a graph and G i be a class of graphs for each i ∈ [ k ] . A (G 1 , … , G k) -partition of G is a partition of V(G) into k sets V 1 , … , V k such that, for each j ∈ [ k ] , the graph G [ V j ] induced by V j is a graph in G j . In this paper, we prove that every planar graph without 4-cycles and 6-cycles admits an (F 2 , F) -partition. As a corollary, V(G) can be partitioned into two sets V 1 and V 2 such that V 1 induces a linear forest and V 2 induces a forest if G is a planar graph without 4-cycles and 6-cycles. [ABSTRACT FROM AUTHOR]

An equitable k-partition ( k ≥ 2 ) of a vertex set S is a partition of S into k subsets (may be empty sets) such that the sizes of any two subsets of S differ by at most one. A maximal-m-clique is a clique with m vertices which is not in a larger clique than itself. A local-equitable k-coloring of G is an assignment of k colors to the vertices of G such that, for every maximal clique of G, the coloring of this clique forms an equitable k-partition of itself. Local-equitable coloring of graphs is a generalization of proper vertex coloring of graphs. In K 4 -free planar graphs, the local-equitable 3-coloring is precisely the same as the proper 3-vertex-coloring. The famous Grötzsch Theorem states that triangle-free planar graphs are 3-colorable. In this paper we show that maximal-3-clique-free planar graphs are local-equitable 3-colorable, which is a generalization of Grötzsch Theorem. [ABSTRACT FROM AUTHOR]

We introduce the Burnside chromatic polynomial of a graph that is invariant under a group action. This is a generalization of the Q-chromatic function Zaslavsky introduced for gain graphs. Given a group 핲 acting on a graph G and a 핲-set X, a proper X-coloring is a function with no monochromatic edge orbit. The set of proper colorings is a 핲-set which induces a polynomial function from the Burnside ring of 핲 to itself. In this paper, we study many properties of the Burnside chromatic polynomial, answering some questions of Zaslavsky. [ABSTRACT FROM AUTHOR]

An injective k-edge coloring of a graph G = (V (G) , E (G)) is a k-edge coloring φ of G such that φ (e 1) ≠ φ (e 3) for any three consecutive edges e 1 , e 2 and e 3 of a path or a 3-cycle. The injective edge chromatic index of G, denoted by χ i ′ (G) , is the minimum k such that G has an injective k-edge coloring. In this paper, we consider the injective edge coloring of the generalized Petersen graph P(n, k). We show that χ i ′ (P (n , k)) ≤ 4 if n ≡ 0 (m o d 4) and k ≡ 1 (m o d 2) ; and χ i ′ (P (n , k)) ≤ 5 if n ≡ 2 (m o d 4) and k ≡ 1 (m o d 2) . Moreover, χ i ′ (P (n , 3)) ≤ 5 , χ i ′ (P (2 k + 1 , k)) ≤ 5 and χ i ′ (P (2 k + 2 , k)) ≤ 5 . [ABSTRACT FROM AUTHOR]

The concept of DP-coloring of a graph is a generalization of list coloring introduced by Dvořák and Postle (J. Combin. Theory Ser. B 129, 38–54, 2018). Multiple DP-coloring of graphs, as a generalization of multiple list coloring, was first studied by Bernshteyn, Kostochka and Zhu (J. Graph Theory 93, 203–221, 2020). This paper proves that planar graphs without 3-cycles and normally adjacent 4-cycles are (7m, 2m)-DP-colorable for every integer m. As a consequence, the strong fractional choice number of any planar graph without 3-cycles and normally adjacent 4-cycles is at most 7/2. [ABSTRACT FROM AUTHOR]

A nonempty graph is called nicely distance-balanced, respectively, edge distance-balanced, whenever there exist positive integers γV and γE, such that for any two adjacent vertices u, v of Γ, there are exactly γV vertices of Γ, respectively γE edges of Γ, which are closer to v than u. In this paper, we show that Hamming graphs H(n, q) are both nicely distance-balanced and nicely edge distance-balanced. [ABSTRACT FROM AUTHOR]

A dominator coloring (resp. total dominator coloring) of a graph G is a proper coloring of the vertices of G in which each closed neighborhood (resp. open neighborhood) of every vertex of G contains a color class. The dominator chromatic number (resp. total dominator chromatic number) of G is the minimum number of colors required for a dominator coloring (resp. total dominator coloring) of G. In this paper, we determine the dominator chromatic number and total dominator chromatic number of the circulant graph Cn(1, 2). [ABSTRACT FROM AUTHOR]

Given a connected graph G with vertex set V G , a subset I of V G is called independent if there are no edges between any two vertices from I. Let i k (G) be the number of independent sets with cardinality k of G and let i 0 (G) = 1 . The independence polynomial of G is defined as I (G ; x) = ∑ k ⩾ 0 i k (G) x k , where i (G) = I (G ; 1) is called the Merrifield–Simmons index of G. In this paper, some extremal problems on the coefficients of the independence polynomial of bipartite graphs are considered. Firstly, the second largest i k (G) (k ⩾ 2) among all bipartite graphs is determined, and the graph which simultaneously minimizes all coefficients of I(G; x) among all bipartite graphs is characterized. Secondly, the largest i k (G) (k ⩾ 2) among all bipartite graphs with at least one cycle is determined, and the unique graph which minimizes all coefficients of I(G; x) among all bipartite graphs with given matching number (resp. diameter at most four, connectivity) is characterized as well. [ABSTRACT FROM AUTHOR]

A path in a vertex-coloured graph is called conflict-free if there is a colour used on exactly one of its vertices. A vertex-coloured graph is said to be conflict-free vertex-connected if any two distinct vertices of the graph are connected by at least one conflict-free vertex-path. The conflict-free vertex-connection number, denoted by vcfc(G), is the smallest number of colours needed in order to make G conflict-free vertex-connected. Our main result of this paper is the following: Let G be a connected graph of order n ≥ 11 . If δ (G) ≥ n 5 , then v c f c (G) ≤ 3 . Moreover, we show that both bounds, on the order n and the minimum degree δ (G) , are tight. Furthermore, we generalize our result by requiring minimum degree-sum conditions for pairs, triples or quadruples of independent vertices. [ABSTRACT FROM AUTHOR]

A t-tone k-coloring of a graph G is a function f : V (G) → [ k ] t such that | f (u) ∩ f (v) | < d (u , v) for all u , v ∈ V (G) with u ≠ v . We write [k] as shorthand for { 1 , … , k } and denote by [ k ] t the family of t-element subset of [k]. The t-tone chromatic number of G, denoted τ t (G) , is the minimum k such that G has a t-tone k-coloring. Cranston, Kim, and Kinnersley proved that if G is a graph with Δ (G) ≤ 3 , then τ 2 (G) ≤ 8 . In this paper, we consider 3-tone coloring of graphs G with Δ (G) ≤ 3 . The previous best result was that τ 3 (G) ≤ 36 ; here we show that τ 3 (G) ≤ 21 . [ABSTRACT FROM AUTHOR]

Oriented coloring of an oriented graph G is an arc-preserving homomorphism from G into a tournament H. We say that the graph H is universal for a family of oriented graphs C if for every G ∈ C there exists a homomorphism from G into H. We are interested in finding a universal graph for the family of orientations of cubic graphs. In this paper we present constructive proof that: if there exists a universal graph H on 7 vertices for every orientation of cubic graphs, then minimum out-degree and minimum in-degree of H are equal to 2. That gives a negative answer to the question presented in Pinlou’s PHD thesis. [ABSTRACT FROM AUTHOR]