Proof of a tiling conjecture of Komlós

A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n‐vertex graph of minimum degree at least (1 ? (1/χ_cr(H)))n, where χ_cr(H) denotes the critical chromatic number of H, then G contains an H‐matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180–205, 2003     

Equitable coloring of random graphs

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable coloring of a graph G with k colors is said to be the equitable chromatic number of G and is denoted by χ₌(G). The least positive integer k such that for any k′ ≥ k there exists an equitable coloring of a graph G with k′ colors is said to be the equitable chromatic threshold of G and is denoted by χ₌*(G). In this paper, we investigate the asymptotic behavior of these coloring parameters in the probability space G(n,p) of random graphs. We prove that if n^?1/5+? < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) = (1 + o(1))χ(G(n,p)) holds (where χ(G(n,p)) is the ordinary chromatic number of G(n,p)). We also show that there exists a constant C such that if C/n < p < 0.99, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) ≤ (2 + o(1))χ(G(n,p)). Concerning the equitable chromatic threshold, we prove that if n^?(1??) < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌* (G(n,p)) ≤ (2 + o(1))χ(G(n,p)) holds, and if < p < 0.99 for some 0 < ?, then almost surely we have χ(G(n,p)) ≤ χ₌*(G(n,p)) = O_?(χ(G(n,p))). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Posets and planar graphs

A k-decomposition (G₁,…,G_k) of a graph G is a partition of its edge set to form k spanning subgraphs G₁,…,G_k. The classical theorem of Nordhaus and Gaddum bounds χ(G₁) + χ(G₂) and χ(G₁)χ(G₂) over all 2-decompositions of K_n. For a graph parameter p, let p(k;G) denote the maximum of over all k-decompositions of the graph G. The clique number ω, chromatic number χ, list chromatic number χℓ, and Szekeres–Wilf number σ satisfy ω(2;K_n) = χ(2;K_n) = χℓ(2;K_n) = σ(2;K_n) = n + 1. We obtain lower and upper bounds for ω(k;K_n), χ(k;K_n), χℓ(k;K_n), and σ(k;K_n). The last three behave differently for large k. We also obtain lower and upper bounds for the maximum of χ(k;G) over all graphs embedded on a given surface. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On the complexity of the circular chromatic number

Circular chromatic number, χ_c is a natural generalization of chromatic number. It is known that it is NP ‐hard to determine whether or not an arbitrary graph G satisfies χ(G)=χ_c(G). In this paper we prove that this problem is NP ‐hard even if the chromatic number of the graph is known. This answers a question of Xuding Zhu. Also we prove that for all positive integers k ≥ 2 and n ≥ 3, for a given graph G with χ(G) = n, it is NP ‐complete to verify if . © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 226–230, 2004     

On the Ramsey number of the triangle and the cube

The Ramsey number r(K ₃,Q _n ) is the smallest integer N such that every red-blue colouring of the edges of the complete graph K _N contains either a red n-dimensional hypercube, or a blue triangle. Almost thirty years ago, Burr and Erd?s conjectured that r(K ₃,Q _n )=2 ⁿ⁺¹?1 for every n∈?, but the first non-trivial upper bound was obtained only recently, by Conlon, Fox, Lee and Sudakov, who proved that r(K ₃,Q _n )?7000·2 ⁿ . Here we show that r(K ₃,Q _n )=(1+o(1))2 ⁿ⁺¹ as n→∞.     

On the Chromatic Number of the Square of the Kneser Graph <Emphasis Type="Italic">K</Emphasis>(2<Emphasis Type="Italic">k</Emphasis>+1, <Emphasis Type="Italic">k</Emphasis>)

The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n-element set, with two vertices adjacent if the sets are disjoint. The chromatic number of the Kneser graph K(n, k) is n–2k+2. Zoltán Füredi raised the question of determining the chromatic number of the square of the Kneser graph, where the square of a graph is the graph obtained by adding edges joining vertices at distance at most 2. We prove that (K²(2k+1, k))4k when k is odd and (K²(2k+1, k))4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on (K²(2k+1, k)), and we find the exact maximum size of an intersecting family of 4-sets in a 9-element set such that no two members of the family share three elements.This work was partially supported by NSF grant DMS-0099608Final version received: April 23, 2003     

Tripartite Ramsey numbers for paths

In this article, we study the tripartite Ramsey numbers of paths. We show that in any two‐coloring of the edges of the complete tripartite graph K(n, n, n) there is a monochromatic path of length (1 ? o(1))2n. Since R(P_2n+1,P_2n+1)=3n, this means that the length of the longest monochromatic path is about the same when two‐colorings of K_3n and K(n, n, n) are considered. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 164–174, 2007     

Random lifts of graphs: Independence and chromatic number

For a graph G, a random n‐lift of G has the vertex set V(G)×[n] and for each edge [u, v] ∈ E(G), there is a random matching between {u}×[n] and {v}×[n]. We present bounds on the chromatic number and on the independence number of typical random lifts, with G fixed and n→∞. For the independence number, upper and lower bounds are obtained as solutions to certain optimization problems on the base graph. For a base graph G with chromatic number χ and fractional chromatic number χ_f, we show that the chromatic number of typical lifts is bounded from below by const ? and also by const ? χ_f/log²χ_f (trivially, it is bounded by χ from above). We have examples of graphs where the chromatic number of the lift equals χ almost surely, and others where it is a.s. O(χ/logχ). Many interesting problems remain open. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 1–22, 2002     

The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.     

Inequalities for the first‐fit chromatic number

The First‐Fit (or Grundy) chromatic number of G, written as χ_FF(G), is defined as the maximum number of classes in an ordered partition of V(G) into independent sets so that each vertex has a neighbor in each set earlier than its own. The well‐known Nordhaus‐‐Gaddum inequality states that the sum of the ordinary chromatic numbers of an n‐vertex graph and its complement is at most n + 1. Zaker suggested finding the analogous inequality for the First‐Fit chromatic number. We show for n ≥ 10 that ?(5n + 2)/4? is an upper bound, and this is sharp. We extend the problem for multicolorings as well and prove asymptotic results for infinitely many cases. We also show that the smallest order of C₄‐free bipartite graphs with χ_FF(G) = k is asymptotically 2k² (the upper bound answers a problem of Zaker [9]). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 75–88, 2008     

The chromatic Ramsey number of odd wheels

We prove that the chromatic Ramsey number of every odd wheel W_{2k+ 1}, k?2 is 14. That is, for every odd wheel W_{2k+ 1}, there exists a 14‐chromatic graph F such that when the edges of F are two‐coloured, there is a monochromatic copy of W_{2k+ 1} in F, and no graph F with chromatic number 13 has the same property. We ask whether a natural extension of odd wheels to the family of generalized Mycielski graphs could help to prove the Burr–Erd?s–Lovász conjecture on the minimum possible chromatic Ramsey number of an n‐chromatic graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:198‐205, 2012     

Extremal problems on set systems

For a family $\boldmath{F}(k) = \{{\mathcal F}_1^{(k)}, {\mathcal F}_2^{(k)},\ldots,{\mathcal F}_t^{(k)}\}$ of k‐uniform hypergraphs let ex (n, F (k)) denote the maximum number of k‐tuples which a k‐uniform hypergraph on n vertices may have, while not containing any member of F (k). Let r_k(n) denote the maximum cardinality of a set of integers Z?[n], where Z contains no arithmetic progression of length k. For any k≥3 we introduce families $\boldmath{F}(k) = \{{\mathcal F}_1^{(k)},{\mathcal F}_2^{(k)}\}$ and prove that n^k?2r_k(n)≤ex (n_k², F (k))≤c_kn^k?1 holds. We conjecture that ex(n, F (k))=o(n^k?1) holds. If true, this would imply a celebrated result of Szemerédi stating that r_k(n)=o(n). By an earlier result o Ruzsa and Szemerédi, our conjecture is known to be true for k=3. The main objective of this article is to verify the conjecture for k=4. We also consider some related problems. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 131–164, 2002.     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Euler Tours of Maximum Girth in K2 n +1 and K2 n ,2 n

Given an eulerian graph G and an Euler tour T of G, the girth of T, denoted by g(T), is the minimum integer k such that some segment of k+1 consecutive vertices of T is a cycle of length k in G. Let g^E(G)= maxg(T) where the maximum is taken over all Euler tours of G.We prove that g^E(K_2n,2n)=4n–4 and 2n–3g^E(K_2n+1)2n–1 for any n2. We also show that g^E(K₇)=4. We use these results to prove the following:1)The graph K_2n,2n can be decomposed into edge disjoint paths of length k if and only if k4n–1 and the number of edges in K_2n,2n is divisible by k.2)The graph K_2n+1 can be decomposed into edge disjoint paths of length k if and only if k2n and the number edges in K_2n+1 is divisible by k.     

A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a^′(G). Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K_n,n. Alon, McDiarmid and Reed observed that a^′(K_p−1,p−1)=p for every prime p. In this paper we prove that a^′(K_p,p)≤p+2=Δ+2 when p is prime. Basavaraju, Chandran and Kummini proved that a^′(K_n,n)≥n+2=Δ+2 when n is odd, which combined with our result implies that a^′(K_p,p)=p+2=Δ+2 when p is an odd prime. Moreover we show that if we remove any edge from K_p,p, the resulting graph is acyclically Δ+1=p+1-edge-colorable.     

Packing Triangles in K 4-Free Graphs

Paul Erd?s conjectured that every K ₄-free graph of order n and size ${k + \lfloor n^2/4\rfloor}$ contains at least k edge disjoint triangles. In this note, we prove that such a graph contains at least 32k/35 + o(n ²) edge disjoint triangles and prove his conjecture for k ≥  0.077n ².     

List‐coloring the square of a subcubic graph

The square G² of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G²) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G² equals the chromatic number of G², that is, χ_l(G²) = χ(G²) for all G. If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ(G) = 3 satisfies χ_l(G²) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ(G) = 3 other than the Petersen graph satisfies χ_l(G²) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 7, then χ_l(G²) ≤ 7. Dvo?ák, ?krekovski, and Tancer showed that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 10, then χ_l(G²) ≤6. We improve the girth bound to show that if G is a planar graph with Δ(G) = 3 and g(G) ≥ 9, then χ_l(G²) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008     

The density of rational points on non-singular hypersurfaces

LetF(x) =F[x₁,…,x_n]∈ℤ[x₁,…,x_n] be a non-singular form of degree d≥2, and letN(F, X)=#{xεℤ ⁿ ;F(x)=0, |x|⩽X}, where . It was shown by Fujiwara [4] [Upper bounds for the number of lattice points on hypersurfaces,Number theory and combinatorics, Japan, 1984, (World Scientific Publishing Co., Singapore, 1985)] thatN(F, X)≪X ^n−2+2/n for any fixed formF. It is shown here that the exponent may be reduced ton - 2 + 2/(n + 1), forn ≥ 4, and ton - 3 + 15/(n + 5) forn ≥ 8 andd ≥ 3. It is conjectured that the exponentn - 2 + ε is admissable as soon asn ≥ 3. Thus the conjecture is established forn ≥ 10. The proof uses Deligne’s bounds for exponential sums and for the number of points on hypersurfaces over finite fields. However a composite modulus is used so that one can apply the ‘q-analogue’ of van der Corput’s AB process. Dedicated to the memory of Professor K G Ramanathan