Subgraphs in vertex neighborhoods of Kr‐free graphs

In a K_r‐free graph, the neighborhood of every vertex induces a K_{r ? 1}‐free subgraph. The K_r‐free graphs with the converse property that every induced K_{r ? 1}‐free subgraph is contained in the neighborhood of a vertex are characterized, based on the characterization in the case r ? 3 due to Pach [ 8 ]. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 29–38, 2004     

Dense graphs with small clique number

We consider the structure of K_r‐free graphs with large minimum degree, and show that such graphs with minimum degree δ>(2r ? 5)n/(2r ? 3) are homomorphic to the join K_{r ? 3}∨H, where H is a triangle‐free graph. In particular this allows us to generalize results from triangle‐free graphs and show that K_r‐free graphs with such a minimum degree have chromatic number at most r +1. We also consider the minimum‐degree thresholds for related properties. Copyright © 2010 John Wiley & Sons, Ltd. 66:319‐331, 2011     

The Ramsey number for a cycle of length five vs. a complete graph of order six

It has been conjectured that r(C_m, K_n) = (m − 1)(n − 1) + 1 for all m ≥ n ≥ 4. This has been proved recently for n = 4 and n = 5. In this paper, we prove that r(C₅, K₆) = 21. This raises the possibility that r(C_m, K₆) = 5m − 4 for all m ≥ 5. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 99–108, 2000     

All cycle‐complete graph Ramsey numbers r(Cm,K6)

The cycle‐complete graph Ramsey number r(C_m, K_n) is the smallest integer N such that every graph G of order N contains a cycle C_m on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(C_m, K_n) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C₃, K₃) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n² ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003     

Tracks emerging by forcing Langton's ant with binary sequences

The well‐known “ant” defined by C. Langton on a grid with black and white squares is forced by periodical binary sequences {r_m}, as follows: i) The ant turns 90° to the left (right) if it enters a white (black) square and if {r_m} = 0 (Langton's case); and ii) the directions are reversed if {r_m} = 1; in both cases the color of the square is inverted as the ant proceeds. Changing the sequences {r_m}, we obtain a plethora of different, periodical tracks. Thousands of runs, some of them differing only by one bit, never rendered the same pattern. Also, an ant moving from a white to a black domain may experience reflection, refraction or sliding on the black‐white‐border. © 2006 Wiley Periodicals, Inc. Complexity 11: 27–32, 2006     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

A note on the girth‐doubling construction for polygonal graphs

A near‐polygonal graph is a graph Γ which has a set ?? of m‐cycles for some positive integer m such that each 2‐path of Γ is contained in exactly one cycle in ??. If m is the girth of Γ then the graph is called polygonal. Given a polygonal graph Γ of valency r and girth m, Archdeacon and Perkel proved the existence of a polygonal graph Γ₂ of valency r and girth 2m. We will show that this construction can be extended to one that yields a polygonal graph Γ₃ of valency r and girth 3m, but that making the cycles any longer with this construction does not yield a polygonal graph. We also show that if Aut(Γ) is 2‐arc transitive, so is Aut(Γ_k) for k = 2, 3. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 246‐254, 2011     

Off‐diagonal and asymptotic results on the Ramsey number r(K2,m,K2,n)

An upper bound on the Ramsey number r(K_2,n‐s,K_2,n) where s ≥ 2 is presented. Considering certain r(K_2,n‐s,K_2,n)‐colorings obtained from strongly regular graphs, we additionally prove that this bound matches the exact value of r(K_2,n‐s,K_2,n) in infinitely many cases if holds. Moreover, the asymptotic behavior of r(K_2,m,K_2,n) is studied for n being sufficiently large depending on m. We conclude with a table of all known Ramsey numbers r(K_2,m,K_2,n) where m,n ≤ 10. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 252–268, 2003     

Every 4‐Colorable Graph With Maximum Degree 4 Has an Equitable 4‐Coloring

Chen et al., conjectured that for r≥3, the only connected graphs with maximum degree at most r that are not equitably r‐colorable are K_{r, r} (for odd r) and K_{r + 1}. If true, this would be a joint strengthening of the Hajnal–Szemerédi theorem and Brooks' theorem. Chen et al., proved that their conjecture holds for r = 3. In this article we study properties of the hypothetical minimum counter‐examples to this conjecture and the structure of “optimal” colorings of such graphs. Using these properties and structure, we show that the Chen–Lih–Wu Conjecture holds for r≤4. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:31–48, 2012     

Line graphs of bipartite graphs with Hamiltonian paths

It is shown that, if t is an integer ≥3 and not equal to 7 or 8, then there is a unique maximal graph having the path P_t as a star complement for the eigenvalue ?2. The maximal graph is the line graph of K_m,m if t = 2m?1, and of K_m,m+1 if t = 2m. This result yields a characterization of L(G ) when G is a (t + 1)‐vertex bipartite graph with a Hamiltonian path. The graphs with star complement P_r ∪ P_s or P_r ∪ C_s for ?2 are also determined. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 137–149, 2003     

Cyclic even cycle systems of the complete graph

In this article, it is proved that for each even integer m?4 and each admissible value n with n>2m, there exists a cyclic m‐cycle system of K_n, which almost resolves the existence problem for cyclic m‐cycle systems of K_n with m even. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:23–39, 2012     

Local and global existence of solutions to a quasilinear degenerate chemotaxis system with unbounded initial data

This paper is concerned with local and global existence of solutions to the parabolic‐elliptic chemotaxis system . Marinoschi (J. Math. Anal. Appl. 2013; 402:415–439) established an abstract approach using nonlinear m‐accretive operators to giving existence of local solutions to this system when 0 < D₀≤D′(r)≤D_∞<∞ and (r₁,r₂)?K(r₁,r₂)r₁ is Lipschitz continuous on , provided that the initial data is assumed to be small. The smallness assumption on the initial data was recently removed (J. Math. Anal. Appl. 2014; 419:756–774). However the case of non‐Lipschitz and degenerate diffusion, such as D(r) = r^m(m > 1), is left incomplete. This paper presents the local and global solvability of the system with non‐Lipschitz and degenerate diffusion by applying (J. Math. Anal. Appl. 2013; 402:415–439) and (J. Math. Anal. Appl. 2014; 419:756–774) to an approximate system. In particular, the result in the present paper does not require any properties of boundedness, smoothness and radial symmetry of initial data. This makes it difficult to deal with nonlinearity. Copyright © 2015 John Wiley & Sons, Ltd.     

Extremal graphs without a semi‐topological wheel

For 2≤r∈?, let S_r denote the class of graphs consisting of subdivisions of the wheel graph with r spokes in which the spoke edges are left undivided. Let ex(n, S_r) denote the maximum number of edges of a graph containing no S_r‐subgraph, and let Ex(n, S_r) denote the set of all n‐vertex graphs containing no S_r‐subgraph that are of size ex(n, S_r). In this paper, a conjecture is put forth stating that for r≥3 and n≥2r + 1, ex(n, S_r) = (r ? 1)n ? ?(r ? 1)(r ? 3/2)? and for r≥4, Ex(n, S_r) consists of a single graph which is the graph obtained from K_{r ? 1, n ? r + 1} by adding a maximum matching to the color class of cardinality r ? 1. A previous result of C. Thomassen [A minimal condition implying a special K₄‐subdivision, Archiv Math 25 (1974), 210–215] implies that this conjecture is true for r = 3. In this paper it is shown to hold for r = 4. © 2011 Wiley Periodicals, Inc. J Graph Theory 68:326‐339, 2011     

On the neutrix composition of the distributions x −s ln m |x| and x r

Let F be a distribution and let f be a locally summable function. The distribution F(f) is defined as the neutrix limit of the sequence {F _n (f)}, where F _n (x) = F(x) * δ _n (x) and {δ _n (x)} is a certain sequence of infinitely differentiable functions converging to the Dirac delta-function δ(x). The composition of the distributions x ^?s ln ^m |x| and x ^r is proved to exist and be equal to r ^m x ^?rs ln ^m |x| for r, s, m = 2, 3….     

A Note on Cyclic m-cycle Systems of K r(m)

It was proved by Buratti and Del Fra that for each pair of odd integers r and m, there exists a cyclic m-cycle system of the balanced complete r-partite graph K_r(m) except for the case when r=m=3. In this note, we study the existence of a cyclic m-cycle system of K_r(m) where r or m is even. Combining the work of Buratti and Del Fra, we prove that cyclic m-cycle systems of K_r(m) exist if and only if (a) K_r(m) is an even graph (b) (r, m)≠ (3, 3) and (c) (r,m)≢ (t , 2) (mod 4) where t ∈ {2,3}.     

Circular consecutive choosability of k‐choosable graphs

Let S(r) denote a circle of circumference r. The circular consecutive choosability ch_cc(G) of a graph G is the least real number t such that for any r≥χ_c(G), if each vertex v is assigned a closed interval L(v) of length t on S(r), then there is a circular r‐coloring f of G such that f(v)∈L(v). We investigate, for a graph, the relations between its circular consecutive choosability and choosability. It is proved that for any positive integer k, if a graph G is k‐choosable, then ch_cc(G)?k + 1 ? 1/k; moreover, the bound is sharp for k≥3. For k = 2, it is proved that if G is 2‐choosable then ch_cc(G)?2, while the equality holds if and only if G contains a cycle. In addition, we prove that there exist circular consecutive 2‐choosable graphs which are not 2‐choosable. In particular, it is shown that ch_cc(G) = 2 holds for all cycles and for K_{2, n} with n≥2. On the other hand, we prove that ch_cc(G)>2 holds for many generalized theta graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 178‐197, 2011     

Continuous k‐to‐1 functions between complete graphs whose orders are of a different parity

A function between graphs is k‐to‐1 if each point in the codomain has precisely k pre‐images in the domain. Given two graphs, G and H, and an integer k≥1, and considering G and H as subsets of ?³, there may or may not be a k‐to‐1 continuous function (i.e. a k‐to‐1 map in the usual topological sense) from G onto H. In this paper we consider graphs G and H whose order is of a different parity and determine the even and odd values of k for which there exists a k‐to‐1 map from G onto H. We first consider k‐to‐1 maps from K_2r onto K_2s+1 and prove that for 1≤r≤s, (r, s)≠(1, 1), there is a continuous k‐to‐1 map for k even if and only if k≥2s and for k odd if and only if k≥?s?_o (where ?s?_o indicates the next odd integer greater than or equal to s). We then consider k‐to‐1 maps from K_2s+1 onto K_2s. We show that for 1≤r<s, such a map exists for even values of k if and only if k≥2s. We also prove that whatever the values of r and s are, no such k‐to‐1 map exists for odd values of k. To conclude, we give all triples (n, k, m) for which there is a k‐to‐1 map from K_n onto K_m in the case when n≤m. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 35–60, 2010.     

On Kummer extensions of the power series field

In this paper we study the Kummer extensions K ′ of a power series field K = k ((X₁, …, X_r)), where k is an algebraically closed field of arbitrary characteristic, with special emphasis in the case where K ′ is generated by a Puiseux power series. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Basis Number of Some Special Non-Planar Graphs

The basis number of a graph G was defined by Schmeichel to be the least integer h such that G has an h-fold basis for its cycle space. He proved that for m, n 5, the basis number b(K _m,n ) of the complete bipartite graph K _m,n is equal to 4 except for K _6,10, K _5,n and K _6,n with n = 5, 6, 7, 8. We determine the basis number of some particular non-planar graphs such as K _5,n and K _6,n , n = 5, 6, 7, 8, and r-cages for r = 5, 6, 7, 8, and the Robertson graph.     

Limit theorems for monochromatic stars

Let T(K_1,r,G_n) be the number of monochromatic copies of the r‐star K_1,r in a uniformly random coloring of the vertices of the graph G_n. In this paper we provide a complete characterization of the limiting distribution of T(K_1,r,G_n), in the regime where is bounded, for any growing sequence of graphs G_n. The asymptotic distribution is a sum of mutually independent components, each term of which is a polynomial of a single Poisson random variable of degree at most r. Conversely, any limiting distribution of T(K_1,r,G_n) has a representation of this form. Examples and connections to the birthday problem are discussed.