BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
For bipartite graphs G and H and a positive integer m, the m-bipartite Ramsey number BRm(G,H) of G and H is the smallest integer n, such that every red-blue coloring of Km,n results in a red G or a blue H. Zhenming Bi, Gary Chartrand and Ping Zhang in \cite{bi2018another} evaluate this numbers for all positive integers m when G=K2,2 and H∈{K2,3,K3,3}, especially in a long and hard argument they showed that BR5(K2,2,K3,3)=BR6(K2,2,K3,3)=12 and BR7(K2,2,K3,3)=BR8(K2,2,K3,3)=9. In this article, by a short and easy argument we determine the exact value of BRm(K2,2,K3,3) for each m≥1.
Let H=(V(H),E(H)) be a graph. A k-coloring of H is a mapping π:V(H)⟶{1,2,…,k} so that each color class induces a K2-free subgraph. For a graph G of order at least 2, a G-free k-coloring of H is a mapping π:V(H)⟶{1,2,…,k} so that the subgraph of H induced by each color class of π is G-free, i.e. contains no copy of G. The G-free chromatic number of H is the minimum number k so that there is a G-free k-coloring of H, denoted by χG(H). A graph H is uniquely k-G-free colouring if χG(H)=k and every k-G-free colouring of H produces the same color classes. A graph H is minimal with respect to G-free, or G-free-minimal, if for every edges of E(H) we have χG(H∖{e})=χG(H)−1. In this paper we give some bounds and attribute about uniquely k-G-free colouring and k-G-free-minimal.
Assume that Kj×n be a complete, multipartite graph consisting of j partite sets and n vertices in each partite set. For given graphs G1,G2,…,Gn, the multipartite Ramsey number (M-R-number) mj(G1,G2,…,Gn) is the smallest integer t such that for any n-edge-coloring (G1,G2,…,Gn) of the edges of Kj×t, Gi contains a monochromatic copy of Gi for at least one i. The size of M-R-number mj(nK2,Cm) for j,n≥2 and 4≤m≤6, the size of M-R-number mj(nK2,C7) for j≥2 and n≥2, the size of M-R-number mj(nK2,K3), for each j,n≥2, the size of M-R-number mj(K3,K3,n1K2,n2K,…,niK2) for j≤6 and i,ni≥1 and the size of M-R-number mj(K3,K3,nK2) for j≥2 and n≥1 have been computed in several papers up to now. In this article we obtain the values of M-R-number mj(Km,nK2), for each j,n≥2 and each m≥4.
Let H=(V(H),E(H)) be a graph. A k-coloring of H is a mapping π:V(H)⟶{1,2,…,k}, if each color class induces a K2-free subgraph. For a graph G of order at least 2, a G-free k-coloring of H, is a mapping π:V(H)⟶{1,2,…,k}, so that the induced subgraph by each color class of π, contains no copy of G. The G-free chromatic number of H, is the minimum number k, so that it has a G-free k-coloring, and denoted by χG(H). In this paper, we give some bounds and attributes on the G-free chromatic number of graphs, in terms of the number of vertices, maximum degree, minimum degree, and chromatic number. Our main results are the Nordhaus-Gaddum-type theorem for the $\G$-free chromatic number of a graph.
For given graph H and graphical property P, the conditional chromatic number χ(H,P) of H, is the smallest number k, so that V(H) can be decomposed into sets V1,V2,…,Vk, in which H[Vi] satisfies the property P, for each 1≤i≤k. When property P be that each color class contains no copy of G, we write χG(H) instead of χ(G,P), which is called the G-free chromatic number. Due to this, we say H has a k-G-free coloring if there is a map c:V(H)⟶{1,…,k}, so that each of the color classes of c be G-free. Assume that for each vertex v of a graph H is assigned a set L(V) of colors, called a color list. Set g(L)={g(v):v∈V(H)}, that is the set of colors chosen for the vertices of H under g. An L-coloring g is called G-free, so that: \begin{itemize} \item g(v)∈L(v), for any v∈V(H). \item H[Vi] is G-free for each i=1,2,…,L. \end{itemize} If there exists an L-coloring of H, then H is called L-G-free-colorable. A graph H is said to be k-G-free-choosable if there exists an L-coloring for any list-assignment L satisfying ∣L(V)∣≥k for each v∈V(H), and H[Vi] be G-free for each i=1,2,…,L. Let graph H and a collection of graphs $\G$ are given, the $χ_{\G}^L(H)$ of H is the last integer k, so that H is k-$\G$-free-choosable i.e. H[Vi] is $\G$-free for each i=1,2,…,k i.e. contains no copy of any member of $\G$. In this article, we show that χGL(H)=χG(H) for some graph H and G, χGL(H⊕H′)≤χGL(H)+χGL(H′) for each G, H, and H′. Also, we show that $χ_{\G}(H\oplus K_n)=χ^L_{\G}(H\oplus K_n)$, where $\G$ is a collection of all d-regular graphs, and some n.
For given graph H, the independence number α(H) of H, is the size of the maximum independent set of V(H). Finding the maximum independent set in a graph is a NP-hard problem. Another version of the independence number is defined as the size of the maximum induced forest of H, and called the forest number of H, and denoted by f(H). Finding f(H) is also a NP-hard problem. Suppose that H=(V(H),E(H)) be a graph, and $\G$ be a family of graphs, a graph H has a $\G$-free k-coloring if there exists a decomposition of V(H) into sets Vi, i−1,2,…,k, so that G⊈H[Vi] for each i, and $G\in\G$. S⊆V(H) is G-free, where the subgraph of H induced by S, be G-free, i.e. it contains no copy of G. Finding a maximum subset of H, so that H[S] be a G-free graph is a very hard problem as well. In this paper, we study the generalized version of the independence number of a graph. Also giving some bounds about the size of the maximum G-free subset of graphs is another purpose of this article.
In a (G1,G2) coloring of a graph G, every edge of G is in G1 or G2. For two bipartite graphs H1 and H2, the bipartite Ramsey number BR(H1,H2) is the least integer b≥1, such that for every (G1,G2) coloring of the complete bipartite graph Kb,b, results in either H1⊆G1 or H2⊆G2. As another view, for bipartite graphs H1 and H2 and a positive integer m, the m-bipartite Ramsey number BRm(H1,H2) of H1 and H2 is the least integer n, such that every subgraph G of Km,n results in H1⊆G or H2⊆G. The size of m-bipartite Ramsey number BRm(K2,2,K2,2), the size of m-bipartite Ramsey number BRm(K2,2,K3,3) and the size of m-bipartite Ramsey number BRm(K3,3,K3,3) have been computed in several articles up to now. In this paper we determine the exact value of BRm(K2,2,K4,4) for each m≥2.
Given bipartite graphs G1,…,Gn, the bipartite Ramsey number BR(G1,…,Gn) is the last integer b such that any complete bipartite graph Kb,b with edges coloured with colours 1,2,…,n contains a copy of some Gi (1≤i≤n) where all edges of Gi have colour i. As another view of bipartite Ramsey numbers, for given bipartite graphs G1,…,Gn and a positive integer m, the m-bipartite Ramsey number BRm(G1,…,Gn), is defined as the least integer b, such that any complete bipartite graph Km,b with edges coloured with colours 1,2,…,n contains a copy of some Gi (1≤i≤n) where all edges of Gi have colour i. The size of BRm(G1,G2), where G1=K2,2 and G2∈{K3,3,K4,4} for each m and the size of BRm(K3,3,K3,3) and BRm(K2,2,K5,5) for special values of m, have been determined in several article up to now. In this article, we compute the size of BRm(K2,2,K6,6) for some m≥2.
For given graphs G1,G2,…,Gn and any integer j, the size of the multipartite Ramsey number mj(G1,G2,…,Gn) is the smallest positive integer t such that any n-coloring of the edges of Kj×t contains a monochromatic copy of Gi in color i for some i, 1≤i≤n, where Kj×t denotes the complete multipartite graph having j classes with t vertices per each class. In this paper we compute the size of the multipartite Ramsey number mj(K1,2,P4,nK2) for any j,n≥2 and mj(nK2,C7), for any j≤4 and n≥2.
As an extension of the Brooks theorem, Catlin in 1979 showed that if H is neither an odd cycle nor a complete graph with maximum degree Δ(H), then H has a vertex Δ(H)-coloring such that one of the color classes is a maximum independent set. Let G be a connected graph of order at least 2. A G-free k-coloring of a graph H is a partition of the vertex set of H into V1,…,Vk such that H[Vi], the subgraph induced on Vi, does not contain any subgraph isomorphic to G. As a generalization of Catlin's theorem we show that a graph H has a G-free ⌈δ(G)Δ(H)⌉-coloring for which one of the color classes is a maximum G-free subset of V(H) if H satisfies the following conditions; (1) H is not isomorphic to G if G is regular, (2) H is not isomorphic to Kkδ(G)+1 if G≃Kδ(G)+1, and (3) H is not an odd cycle if G is isomorphic to K2. Indeed, we show even more, by proving that if G1,…,Gk are connected graphs with minimum degrees d1,…,dk, respectively, and Δ(H)=∑i=1kdk, then there is a partition of vertices of H to V1,…,Vk such that each H[Vi] is Gi-free and moreover one of Vis can be chosen in a way that H[Vi] is a maximum Gi-free subset of V(H) except either k=1 and H is isomorphic to G1, each Gi is isomorphic to Kdi+1 and H is not isomorphic to KΔ(H)+1, or each Gi is isomorphic to K2 and H is not an odd cycle.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.