Search

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]

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]

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]

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]

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]

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]

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]

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

Given a graph G (with multiple edges allowed), a k-restricted edge-cut of G is an edge-cut R ⊆ E (G) of G such that every connected component in G - R has order at least k. A graph G is λ k -connected if k-restricted edge cuts exist. Given an edge-coloring of G, an edge-cut of G will be called heterochromatic if all its edges receive different colors. Given a graph G and an integer k ≥ 2 , let h(G, k) be the minimum integer p such that every p-coloring of the edges of G produces an heterochromatic k-restricted edge-cut of G. In this paper we prove that for a λ k -connected graph G of size m, order n ≥ 3 k - 2 , and with no k-restricted edge-cut of size 1, we have that m - n + min { κ 0 (G) - 2 , t (G , k) } + 2 ≤ h (G , k) ≤ m - n + t (G , k) + 2 , where κ 0 (G) is the vertex-connectivity of G and t(G, k) is the maximum cardinality of a set S ⊆ V (G) such that the connected components in G[S] have order at most k - 1 . As a corollary we see that h (G , k) ≤ m - n + α (G) (k - 1) + 2 , with α (G) the independence number of G. [ABSTRACT FROM AUTHOR]

DP-coloring is a generalization of list coloring that was introduced in 2015 by Dvořák and Postle. The chromatic polynomial of a graph G, denoted P(G, m), is equal to the number of proper m-colorings of G. A well-known tool for computing the chromatic polynomial of graph G is the deletion-contraction formula which relates P(G, m) to the chromatic polynomials of two smaller graphs. The DP color function of a graph G, denoted P DP (G , m) , is a DP-coloring analogue of the chromatic polynomial, and P DP (G , m) is the minimum number of DP-colorings of G over all possible m-fold covers. In this paper we present a deletion-contraction relation for the DP color function. To make this possible, we extend the definition of the DP color function to multigraphs. We also introduce the dual DP color function of a graph G, denoted P DP ∗ (G , m) , which counts the maximum number of DP-colorings of G over certain m-fold covers. We show how the dual DP color function along with our deletion-contraction relation yields a new general lower bound on the DP color function of a graph. [ABSTRACT FROM AUTHOR]

Let λ be a positive integer. An acyclic λ -coloring of a digraph D is a partition of the vertices of D into λ color clases such that the color classes induce acyclic subdigraphs in D. The minimum integer λ for which there exists an acyclic λ -coloring of D is the dichromatic numberdc(D) of D. Let P (D ; λ) be the dichromatic polynomial of D, which is the number of acyclic λ -colorings of D. In this paper, a recursive formula for P (D ; λ) is given. The coefficients of the polynomial P (D ; λ) are studied. The dichromatic polynomial of a digraph D is related to the structure of its underlying graph UG(D). Also, we study dichromatic equivalently and dichromatically unique digraphs. [ABSTRACT FROM AUTHOR]

Let G be a graph with an edge-coloring c, and let δ c (G) denote the minimum color-degree of G. A subgraph of G is called rainbow if any two edges of the subgraph have distinct colors. In this paper, we consider color-degree conditions for the existence of rainbow triangles in edge-colored graphs. At first, we give a new proof for characterizing all extremal graphs G with δ c (G) ≥ n 2 that do not contain rainbow triangles, a known result due to Li et al. Then, we characterize all complete graphs G without rainbow triangles under the condition δ c (G) = l o g 2 n , extending a result due to Li, Fujita and Zhang. Hu, Li and Yang showed that G contains two vertex-disjoint rainbow triangles if δ c (G) ≥ n + 2 2 when n ≥ 20 . We slightly refine their result by showing that the result also holds for n ≥ 6 , filling the gap of n from 6 to 20. Finally, we prove that if δ c (G) ≥ n + k 2 then every vertex of an edge-colored complete graph G is contained in at least k rainbow triangles, generalizing a result due to Fujita and Magnant. At the end, we mention some open problems. [ABSTRACT FROM AUTHOR]

Let H be a graph possibly with loops and G a multigraph without loops. G is said to be H-colored if there exists a function c: E(G) → V(H). A cycle ( v 0 , e 0 , v 1 , e 1 , ... , e k - 1 , v k = v 0 ) in G, where e i = v i v i + 1 for every i in {0, ... , k - 1 }, is an H-cycle if and only if (c( e 0 ), a 0 , c( e 1 ), ... , c( e k - 2 ), a k - 2 , c( e k - 1 ), a k - 1 , c( e 0 )) is a walk in H, with a i = c( e i )c( e i + 1 ) for every i in {0, ... , k - 1 } (indices modulo k). If H is a complete graph without loops, an H-walk is called properly colored walk. The problem of check whether an edge-colored graph G contains a properly colored cycle was studied first by Grossman and Häggkvist. Subsequently Yeo gave a sufficient condition which guarantee the existence of a properly colored cycle. In this paper we will extend Yeo's result for the case where stronger requirements are enforced for a properly colored cycle to be eligible, based on the adjacencies of a graph whose vertices are in bijection with the colors. The main result establishes that if H is a graph without loops and G is an H-colored multigraph such that (1) H and G have no isolated vertices, (2) G has no H-cycles and (3) for every x in V(G), G x is a complete k x -partite graph for some k x in N . Then there exists a vertex z in V(G) such that every connected component D of G - z satisfies that {e ∈ E(G) : e = z u for some u in V(D)} is an independent set in G z (where for w in V(G), G w is an associated graph to the vertex w, respect to the H-coloring of G). [ABSTRACT FROM AUTHOR]

A strong edge coloring of a graph G is a proper edge coloring of G such that every color class is an induced matching. The minimum number of colors required is termed the strong chromatic index. In this paper we determine the exact value of the strong chromatic index of all unitary Cayley graphs. Our investigations reveal an underlying product structure from which the unitary Cayley graphs emerge. We then go on to give tight bounds for the strong chromatic index of the Cartesian product of two trees, including an exact formula for the product in the case of stars. Further, we give bounds for the strong chromatic index of the product of a tree with a cycle. For any tree, those bounds may differ from the actual value only by not more than a small additive constant (at most 2 for even cycles and at most 4 for odd cycles), moreover they yield the exact value when the length of the cycle is divisible by 4. [ABSTRACT FROM AUTHOR]

Graphs considered in this paper are finite, undirected and without loops, but with multiple edges. For an integer t ≥ 1 , denote by MG t the class of graphs whose maximum multiplicity is at most t. A graph G is called strictly t-degenerate if every non-empty subgraph H of G contains a vertex v whose degree in H is at most t - 1 . The point partition number χ t (G) of G is the smallest number of colors needed to color the vertices of G so that each vertex receives a color and vertices with the same color induce a strictly t-degenerate subgraph of G. So χ 1 is the chromatic number, and χ 2 is known as the point aboricity. The point partition number χ t with t ≥ 1 was introduced by Lick and White (Can J Math 22:1082–1096, 1970). If H is a simple graph, then tH denotes the graph obtained from H by replacing each edge of H by t parallel edges. Then ω t (G) is the largest integer n such that G contains a t K n as a subgraph. Let G be a graph belonging to MG t . Then ω t (G) ≤ χ t (G) and we say that G is χ t -perfect if every induced subgraph H of G satisfies ω t (H) = χ t (H) . Based on the Strong Perfect Graph Theorem due to Chudnowsky, Robertson, Seymour and Thomas (Ann Math 164:51–229, 2006), we give a characterization of χ t -perfect graphs of MG t by a set of forbidden induced subgraphs (see Theorems 2 and 3). We also discuss some complexity problems for the class of χ t -critical graphs. [ABSTRACT FROM AUTHOR]

In 1988, Beck (J Algebra 116:208–226, 1988) conjectured that the chromatic number and clique number is the same for the graphs associated to any commutative ring with unity. In 1993, Anderson and Naseer (J Algebra 159:500–514, 1993) disproved the conjecture with a counterexample. In this paper, we find the clique number and bounds for the chromatic number of the graph associated with the finite product of commutative rings with unity. Also we show that some of the results, proved in (Anderson and Naseer in J Algebra 159:500–514, 1993, Beck in J Algebra 116:208–226, 1988) are consequences of our results. In addition, we have constructed a new family of counterexamples of the above conjecture. [ABSTRACT FROM AUTHOR]

It is well-known that every triangulation on a closed surface F 2 has a spanning quadrangulation Q, and in particular, Q is bipartite if F 2 is the sphere. In other words, every triangulation on the sphere has a polychromatic 2-coloring, which is a (not necessarily proper) 2-coloring of a graph on a closed surface without a monochromatic face. In this paper, we consider the balancedness of a polychromatic 2-coloring of graphs, that is, whether the difference in size of each color class is at most one. We verify that every 3-colorable triangulation has a balanced polychromatic 2-coloring. On the other hand, we construct an infinite family of triangulations G with order n on the sphere such that for every polychromatic 2-coloring of G, the size of color classes differs at least n 3 - 2 . Then we conjecture that every triangulation on the sphere has a polychromatic 2-coloring whose size of color classes differs at most one-third of the number of vertices, and we give partial solutions for the conjecture. [ABSTRACT FROM AUTHOR]

Let μ (G) denote the mean color number of a graph G. Dong proposed two mean color conjectures. One is that for any graph G and a vertex w in G with d (w) ≥ 1 , if H is a graph obtained from G by deleting all but one of the edges which are incident to w, then μ (G) ≥ μ (H) . The other is that for any graph G and a vertex w in G, μ (G) ≥ μ ((G - w) ∪ K 1) . In this paper, we show that the two conjectures hold under the condition that w is a simplicial vertex in G. And when G is a connected (n, m)-graph and w is not a cut vertex in G with d (w) = n - 1 , if m ≤ (2 2 + 2) n - 4.5 - 2 , the second conjecture holds too. The two conjectures also hold for some special cases, such as wheels and chordal graphs (Dong in J Combin Theory Ser B 87: 348–365, 2003). [ABSTRACT FROM AUTHOR]

We consider a proper coloring of a plane graph such that no face is rainbow, where a face is rainbow if any two vertices on its boundary have distinct colors. Such a coloring is said to be proper anti-rainbow. A plane quadrangulation G is a plane graph in which all faces are bounded by a cycle of length 4. In this paper, we show that the number of colors in a proper anti-rainbow coloring of a plane quadrangulation G does not exceed 3 α (G) / 2 , where α (G) is the independence number of G. Moreover, if the minimum degree of G is 3 or if G is 3-connected, then this bound can be improved to 5 α (G) / 4 or 7 α (G) / 6 + 1 / 3 , respectively. All of these bounds are tight. [ABSTRACT FROM AUTHOR]