Search

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 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]

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]

An i-packing in a graph G is a set of vertices that are pairwise at distance more than i. A packing colouring of G is a partition X = {X1, X2,... , Xk } of V(G) such that each colour class Xi is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χρ(G). In this paper we investigate the existence of trees T for which there is only one packing colouring using χρ(T) colours. For the case χρ(T) = 3, we completely characterise all such trees. As a by-product we obtain sets of uniquely 3-χρ-packable trees with monotone χρ-colouring and non-monotone χρ-colouring respectively. [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 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]

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]

A vertex coloring is called distinguishing if the identity is the only automorphism that can preserve it. The distinguishing threshold θ(G) of a graph G is the minimum number of colors k required that any arbitrary k-coloring of G is distinguishing. In this paper, we calculate the distinguishing threshold of a Cartesian product graph. Moreover, we calculate the number of non-equivalent distinguishing colorings of grids. [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]

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]

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]

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]

In 2017, Dvořák and Postle introduced DP-coloring (known as correspondence coloring) as a generalization of list coloring. Recently, a lot of attention has been put on sufficient conditions for planar graphs to be DP-4-colorable. Liu et al. [17] proved that every planar graph without triangles adjacent to cycles of length five is DP-4-colorable. Let be the family of planar graphs without 3-cycles adjacent to two cycles of length five. In this paper, we prove that every member in is DP-4-colorable, which generalizes a result of [17]. As a consequence, every graph in is 4-choosable. [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]

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]

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]

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]

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]

In this paper, we define new parameters which measure the edge uncolourability of cubic graphs. These parameters count the minimum number of vertex reductions required to render a 3-edge-colourable graph, given a cubic graph G. Two of these parameters we denote as 1r(G) and er(G). We recall as well that the resistance of G, denoted as r(G), counts the minimum number of edges which can be removed from G in order to render 3-edge-colourability. Also, the weak oddness of G denoted as ω′(G) counts the minimum number of odd components in an even factor of G, and the flow resistance of G denoted as rf(G) counts the minimum number of zero edges in a 4-flow of G. Weak oddness and flow resistance are also considered measurements of edge uncolourability in cubic graphs. We conjecture that r(G) > 1r(G) and that r(G) > er(G). We then prove some significant consequences of these conjectures being true with regards to weak oddness and flow resistance. [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]

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 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]

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]

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]

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]

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]

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]

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]

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 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]

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]

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 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]

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]

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]

It is not yet finished to locate the exact value of ex (n ; K 2 , t + 1) in the extremal graph theory. Füredi (J Combin Theory Ser A 75(1):141–144, 1996) proved that the Hyltén-Cavallius’ bound n 4 4 t n - 4 t + 1 + 1 is asymptotically best possible for ex (n ; K 2 , t + 1) . In this paper we investigate the number of copies of K 2 , t + 1 ( t ≥ 2 ) in a graph. We show that an n-vertex graph G contains at least ϵ t + 1 4 t n - 4 t + 1 + 8 t ϵ 2 (t + 1) (n - 1) + 2 ϵ 2 (t + 1) n copies of K 2 , t + 1 provided that | E (G) | = n 4 4 t n - 4 t + 1 + 1 + ϵ , where ϵ > 0 is a real number. Furthermore, we also obtain a formula for the number of copies of K 2 , t + 1 in a graph. [ABSTRACT FROM AUTHOR]