On three color Ramsey numbers R(C4,C4,K1,n)

For $k$ given graphs $G_1,G_2,\dots ,G_k$, $k\ge 2$, the $k$-color Ramsey number, denoted by $R(G_1,G_2,\dots ,G_k)$, is the smallest integer $N$ such that if we arbitrarily color the edges of a complete graph of order $N$ with $k$ colors, then it always contains a monochromatic copy of $G_i$ colored with $i$, for some $1\le i\le k$. Let $C_m$ be a cycle of length $m$ and $K_{1,n}$ a star of order $n+1$. In this paper, firstly we give a general upper bound of $R(C_4,C_4,\dots ,C_4,K_{1,n})$. In particular, for the 3-color case, we have $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+3$ and this bound is tight in some sense. Furthermore, we prove that $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+2$ for all $n={?}^2??$ and $?\ge 2$, and if $?$ is a prime power, then the equality holds.     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

C4-free edge ideals

We discuss the linearity of the minimal free resolution of a power of a monomial edge ideal.     

Multicolor bipartite Ramsey number of C4 and large Kn,n

Let br_k(C₄;K_{n, n}) be the smallest N such that if all edges of K_{N, N} are colored by k + 1 colors, then there is a monochromatic C₄ in one of the first k colors or a monochromatic K_{n, n} in the last color. It is shown that br_k(C₄;K_{n, n}) = Θ(n²/log²n) for k?3, and br₂(C₄;K_{n, n})≥c(n n/log²n)² for large n. The main part of the proof is an algorithm to bound the number of large K_{n, n} in quasi‐random graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 47‐54, 2011     

Connected subgroups of the conformal group C(1, 4)

A method is given for describing maximal subalgebras of rank r, 1 r 4, of the conformal algebra AC(1, 4), which is the maximal invariance algebra of the eikonal equation. With the help of this method a classification is made up to C(1, 4)-equivalence of all maximal subalgebras L of rank 1, 2, 3, and 4 of the algebra AC(1, 4) satisfying the condition L V p₁, P₂, P₃, p₄, where V is the space of translations.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 43, Nos. 7–8, pp. 870–884, July–August, 1991.     

Linearly χ-bounding (P6, C4)-free graphs*

Given two graphs and , a graph is -free if it contains no induced subgraph isomorphic to or . Let and be the path on vertices and the cycle on vertices, respectively. In this paper we show that for any -free graph it holds that , where and are the chromatic number and clique number of , respectively. Our bound is attained by several graphs, for instance, the 5-cycle, the Petersen graph, the Petersen graph with an additional universal vertex, and all -critical -free graphs other than (see Hell and Huang [Discrete Appl. Math. 216 (2017), pp. 211–232]). The new result unifies previously known results on the existence of linear -binding functions for several graph classes. Our proof is based on a novel structure theorem on -free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time -approximation algorithm for coloring -free graphs. Our algorithm computes a coloring with colors for any -free graph in time.     

Classification of Plane Congruences in 4 C4 (I)

Nondegenerate plane congruences in the four-dimensional complex projective space with degenerate general focal conic are classified by using the focal method due to Corrado Segre.     

C4- and D4-Modules via perspective direct summands

In this article, we study the C4- and D4-modules in terms of perspective direct summands, providing new characterizations and results. Endomorphism rings of C4-modules and extensions of right C4-rings are also investigated. Decompositions of C4-modules with restricted ACC on direct summands and D4-modules with restricted DCC on direct summands are obtained.     

Decomposing C4-free graphs under degree constraints

A celebrated theorem of Stiebitz 13 asserts that any graph with minimum degree at least can be partitioned into two parts that induce two subgraphs with minimum degree at least s and t, respectively. This resolved a conjecture of Thomassen. In this article, we prove that for , if a graph G contains no cycle of length four and has minimum degree at least , then G can be partitioned into two parts that induce two subgraphs with minimum degree at least s and t, respectively. This improves the result of Diwan in 5, where he proved the same statement for graphs of girth at least five. Our proof also works for the case of variable functions, in which the bounds are sharp as showing by some polarity graphs.     

C 4p -frame of complete multipartite multigraphs

For two graphs G and H their wreath product ${G \otimes H}$ has the vertex set ${V(G) \times V(H)}$ in which two vertices (g ₁, h ₁) and (g ₂, h ₂) are adjacent whenever ${g_{1}g_{2} \in E(G)}$ or g ₁ =  g ₂ and ${h_{1}h_{2} \in E(H)}$ . Clearly ${K_{m} \otimes I_{n}}$ , where I _n is an independent set on n vertices, is isomorphic to the complete m-partite graph in which each partite set has exactly n vertices. A subgraph of the complete multipartite graph ${K_m \otimes I_n}$ containing vertices of all but one partite set is called partial factor. An H-frame of ${K_m \otimes I_n}$ is a decomposition of ${K_m \otimes I_n}$ into partial factors such that each component of it is isomorphic to H. In this paper, we investigate C _2k -frames of ${(K_m \otimes I_n)(\lambda)}$ , and give some necessary or sufficient conditions for such a frame to exist. In particular, we give a complete solution for the existence of a C _4p -frame of ${(K_m \otimes I_n)(\lambda)}$ , where p is a prime, as follows: For an integer m ≥  3 and a prime p, there exists a C _4p -frame of ${(K_m \otimes I_n)(\lambda)}$ if and only if ${(m-1)n \equiv 0 ({\rm {mod}} {4p})}$ and at least one of m, n must be even, when λ is odd.     

ON TWIN-TRIANGULAR ADDITIVE GROUP ACTIONS ON C4

This paper concerns some of the conditions satisfied by additive group actions on complex affine space which can be written locally as a translation of a variable. Assume X is the affine variety C ⁿ , G_a = (C, +), and σ : G_a × X → X is the action defined by a group monomorphism G _a → Aut _C X. If σ is locally trivial, then the action satisfies what is termed a “GICO” condition.

It will be shown that a large class of G_a -actions on C ⁴, that is, fixed-point free, “twin-triangular” actions with finitely-generated rings of invariants, are at least GICO. Remaining questions are discussed.     

The Number of Triangulations of the Cyclic Polytope C (n , n -4)

We show that the exact number of triangulations of the standard cyclic polytope C(n,n-4) is (n+4)2 ^(n-4)/2 -n if n is even and \left((3n+11)/2\right)2 ^(n-5)/2 -n if n is odd. These formulas were previously conjectured by the second author. Our techniques are based on Gale duality and the concept of virtual chamber. They further provide formulas for the number of triangulations which use a specific simplex. We also compute the maximum number of regular triangulations among all the realizations of the oriented matroid of C(n,n-4) . Received October 24, 2000, and in revised form July 8, 2001. Online publication November 7, 2001.     

C 1 Quintic Splines on Type-4 Tetrahedral Partitions

Starting with a partition of a rectangular box into subboxes, it is shown how to construct a natural tetrahedral (type-4) partition and associated trivariate C ¹ quintic polynomial spline spaces with a variety of useful properties, including stable local bases and full approximation power. It is also shown how the spaces can be used to solve certain Hermite and Lagrange interpolation problems.     

A Construction of Uniquely C4-free colourable Graphs

Abstract

An F-free colouring of a graph G is a partition {V₁,V₂,…,V_n} of the vertex set V(G) of G such that F is not an induced subgraph of G[V_i] for each i. A graph is uniquely F-free colourable if any two .F-free colourings induce the same partition of V(G). We give a constructive proof that uniquely C₄-free colourable graphs exist.