Spread‐out percolation in ℝd

Fix d ≥ 2, and let X be either ℤ^d or the points of a Poisson process in ℝ^d of intensity 1. Given parameters r and p, join each pair of points of X within distance r independently with probability p. This is the simplest case of a “spread‐out” percolation model studied by Penrose [Ann Appl Probab 3 (1993) 253–276], who showed that, as r → ∞, the average degree of the corresponding random graph at the percolation threshold tends to 1, i.e., the percolation threshold and the threshold for criticality of the naturally associated branching process approach one another. Here we show that this result follows immediately from of a general result of [3] on inhomogeneous random graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

On the chromatic number of a random 5‐regular graph

It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is asymptotically almost surely equal to 3, provided a certain four‐variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3‐colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 157–191, 2009     

K4‐free graphs with no odd hole: Even pairs and the circular chromatic number

An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K₄‐free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K₄‐free graph with no odd hole has circular chromatic number strictly smaller than 4. We also exhibit a sequence {H_n} of such graphs with lim_n→∞χ_c(H_n)=4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 303–322, 2010     

Excluding 4‐Wheels

A 4‐wheel is a graph formed by a cycle C and a vertex not in C that has at least four neighbors in C. We prove that a graph G that does not contain a 4‐wheel as a subgraph is 4‐colorable and we describe some structural properties of such a graph.     

On chromatic‐choosable graphs

A graph is chromatic‐choosable if its choice number coincides with its chromatic number. It is shown in this article that, for any graph G, if we join a sufficiently large complete graph to G, then we obtain a chromatic‐choosable graph. As a consequence, if the chromatic number of a graph G is close enough to the number of vertices in G, then G is chromatic‐choosable. We also propose a conjecture related to this fact. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 130–135, 2002     

On the Roots of σ‐Polynomials

Given a graph G of order n, the σ‐polynomial of G is the generating function where is the number of partitions of the vertex set of G into i nonempty independent sets. Such polynomials arise in a natural way from chromatic polynomials. Brenti (Trans Am Math Soc 332 (1992), 729–756) proved that σ‐polynomials of graphs with chromatic number at least had all real roots, and conjectured the same held for chromatic number . We affirm this conjecture.     

6‐regular 4‐critical graph

P. Erd?s conjectured in [2] that r‐regular 4‐critical graphs exist for every r ≥ 3 and noted that no such graphs are known for r ≥ 6. This article contains the first example of a 6‐regular 4‐critical graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 286–291, 2002     

Short odd cycles in 4‐chromatic graphs

It is shown that any 4‐chromatic graph on n vertices contains an odd cycle of length smaller than √8n. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 145–147, 1999     

Large‐deviations/thermodynamic approach to percolation on the complete graph

We present a large‐deviations/thermodynamic approach to the classic problem of percolation on the complete graph. Specifically, we determine the large‐deviation rate function for the probability that the giant component occupies a fixed fraction of the graph while all other components are “small.” One consequence is an immediate derivation of the “cavity” formula for the fraction of vertices in the giant component. As a byproduct of our analysis we compute the large‐deviation rate functions for the probability of the event that the random graph is connected, the event that it contains no cycles and the event that it contains only small components. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

First‐passage percolation on a ladder graph,and the path cost in a VCG auction

This paper studies the time constant for first‐passage percolation, and the Vickrey‐Clarke‐Groves (VCG) payment, for the shortest path on a ladder graph (a width‐2 strip) with random edge costs, treating both in a unified way based on recursive distributional equations. For first‐passage percolation where the edge costs are independent Bernoulli random variables we find the time constant exactly; it is a rational function of the Bernoulli parameter. For first‐passage percolation where the edge costs are uniform random variables we present a reasonably efficient means for obtaining arbitrarily close upper and lower bounds. Using properties of Harris chains we also show that the incremental cost to advance through the medium has a unique stationary distribution, and we compute stochastic lower and upper bounds. We rely on no special properties of the uniform distribution: the same methods could be applied to any well‐behaved, bounded cost distribution. For the VCG payment, with Bernoulli‐distributed costs the payment for an n‐long ladder, divided by n, tends to an explicit rational function of the Bernoulli parameter. Again, our methods apply more generally. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 350‐364, 2011     

Coloring 4‐cycle systems

An m‐cycle system of order n is a partition of the edges of the complete graph K_n into m‐cycles. We investigate k‐colorings of 4‐cycle systems in which no 4‐cycle is monochromatic. For any k ≥ 3, we construct a k‐chromatic 4‐cycle system. We also show that for any k ge; 2, there exists an integer w_k such that for all admissible n ≥ w_k, there is a k‐chromatic 4‐cycle system of order n. © 2005 Wiley Periodicals, Inc. J Combin Designs     

χ‐bounded families of oriented graphs

A famous conjecture of Gyárfás and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star S and integer k, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size k or it contains S as an induced subgraph. As an evidence, we prove that for any oriented star S, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order 3 or S as an induced subdigraph. We then study for which sets of orientations of P₄ (the path on four vertices) similar statements hold. We establish some positive and negative results.     

4‐Coloring P6‐Free Graphs with No Induced 5‐Cycles

We show that the 4‐coloring problem can be solved in polynomial time for graphs with no induced 5‐cycle C₅ and no induced 6‐vertex path P₆     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

Small odd cycles in 4‐chromatic graphs*

It is shown that every 4‐chromatic graph on n vertices contains an odd cycle of length less than . This improves the previous bound given by Nilli [J Graph Theory 3 ( 3 ), 145–147]. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 115–117, 2001     

Planar Digraphs of Digirth Five Are 2‐Colorable

Neumann‐Lara (1985) and ?krekovski conjectured that every planar digraph with digirth at least three is 2‐colorable, meaning that the vertices can be 2‐colored without creating any monochromatic directed cycles. We prove a relaxed version of this conjecture: every planar digraph of digirth at least five is 2‐colorable. The result also holds in the setting of list colorings.     

A Harris‐Kesten theorem for confetti percolation

Percolation properties of the dead leaves model, also known as confetti percolation, are considered. More precisely, we prove that the critical probability for confetti percolation with square‐shaped leaves is 1/2. This result is related to a question of Benjamini and Schramm concerning disk‐shaped leaves and can be seen as a variant of the Harris‐Kesten theorem for bond percolation. The proof is based on techniques developed by Bollobás and Riordan to determine the critical probability for Voronoi and Johnson‐Mehl percolation. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 361–385, 2015     

On the chromatic number of random graphs

We consider random graphs G_n,p with fixed edge-probability p. We refine an argument of Bollobás to show that almost all such graphs have chromatic number equal to n/{2 log_b n ? 2 log_b log_b n + O(1)} where b = 1/(1 ? p).     

On connectivity,conductance and bootstrap percolation for a random k‐out,age‐biased graph

A uniform attachment graph (with parameter k), denoted G_n,k in the paper, is a random graph on the vertex set [n], where each vertex v makes k selections from [v ? 1] uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well‐studied random graphs: k‐out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of G_n,k to show that the conductance of G_n,k is of order . We also study the bootstrap percolation on G_n,k, where r infected neighbors infect a vertex, and show that if the probability of initial infection of a vertex is negligible compared to then with high probability (whp) the disease will not spread to the whole vertex set, and if this probability exceeds by a sub‐logarithmical factor then the disease whp will spread to the whole vertex set.