ω, Δ, and χ

We discuss bounding the chromatic number of a graph by a convex combination of its clique number and its maximum degree plus 1. We will often have recourse to the probabilistic method. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 177–212, 1998     

On σ-equivalence and χ-equivalence of graphs

We define a partial ordering on the set of σ-polynomials as well as a vertex splitting operation on the set of graphs, and introduce the notions of σ-equivalence and σ-uniqueness of graphs. Let σ(G) be the σ-polynomial of a graph G and (OVERBAR)σ(G) = σ(G^c). Let H = (G, v, A, B) be a vertex splitting graph of G. We prove that (OVERBAR)σ(G) ≤ (OVERBAR)σ(H) and the equality holds if and only if every vertex of A is adjacent to every vertex of B. This gives us an effective means to find σ-equivalent and χ-equivalent graphs. A necessary and sufficient condition for a graph to be χ-unique but not σ-unique is also obtained. © 1996 John Wiley & Sons, Inc.     

Amalgams and χ‐Boundedness

A class of graphs is hereditary if it is closed under isomorphism and induced subgraphs. A class of graphs is χ‐bounded if there exists a function such that for all graphs , and all induced subgraphs H of G, we have that . We prove that proper homogeneous sets, clique‐cutsets, and amalgams together preserve χ‐boundedness. More precisely, we show that if and are hereditary classes of graphs such that is χ‐bounded, and such that every graph in either belongs to or admits a proper homogeneous set, a clique‐cutset, or an amalgam, then the class is χ‐bounded. This generalizes a result of [J Combin Theory Ser B 103(5) (2013), 567–586], which states that proper homogeneous sets and clique‐cutsets together preserve χ‐boundedness, as well as a result of [European J Combin 33(4) (2012), 679–683], which states that 1‐joins preserve χ‐boundedness. The house is the complement of the four‐edge path. As an application of our result and of the decomposition theorem for “cap‐free” graphs from [J Graph Theory 30(4) (1999), 289–308], we obtain that if G is a graph that does not contain any subdivision of the house as an induced subgraph, then .     

χ‐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.     

χ‐bounds,operations, and chords

A long unichord in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is long unichord free if it does not contain any long unichord. We prove a structure theorem for long unichord free graph. We give an time algorithm to recognize them. We show that any long unichord free graph G can be colored with at most colors, where ω is the maximum number of pairwise adjacent vertices in G.     

Finding Δ(Σ) for a surface σ of characteristic χ(Σ) = −5

For each surface Σ, we define Δ(Σ) = max{Δ(G)|Gis a class two graph of maximum degree Δ(G) that can be embedded in Σ}. Hence, Vizing's Planar Graph Conjecture can be restated as Δ(Σ) = 5 if Σ is a plane. In this paper, we show that Δ(Σ) = 9 if Σ is a surface of characteristic χ(Σ) = ?5. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:148‐168, 2011     

A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω

In 1998 the second author proved that there is an such that every graph satisfies . The first author recently proved that any graph satisfying contains a stable set intersecting every maximum clique. In this note, we exploit the latter result to give a much shorter, simpler proof of the former. Working from first principles, we omit only some five pages of proofs of known intermediate results (which appear in an extended version of this paper), and the proofs of Hall's Theorem, Brooks' Theorem, the Lovász Local Lemma, and Talagrand's Inequality.     

On effective σ‐boundedness and σ‐compactness

We prove several dichotomy theorems which extend some known results on σ‐bounded and σ‐compact pointsets. In particular we show that, given a finite number of $\Delta ^{1}_{1}$ equivalence relations $\mathrel {\mathsf {F}}_1,\dots ,\mathrel {\mathsf {F}}_n$, any $\Sigma ^{1}_{1}$ set A of the Baire space either is covered by compact $\Delta ^{1}_{1}$ sets and lightface $\Delta ^{1}_{1}$ equivalence classes of the relations $\mathrel {\mathsf {F}}_i$, or A contains a superperfect subset which is pairwise $\mathrel {\mathsf {F}}_i$‐inequivalent for all i = 1, …, n. Further generalizations to $\Sigma ^{1}_{2}$ sets A are obtained.     

Perfect coloring and linearly χ‐bound P6‐free graphs

We derive decomposition theorems for P₆, K₁ + P₄‐free graphs, P₅, K₁ + P₄‐free graphs and P₅, K₁ + C₄‐free graphs, and deduce linear χ‐binding functions for these classes of graphs (here, P_n (C_n) denotes the path (cycle) on n vertices and K₁ + G denotes the graph obtained from G by adding a new vertex and joining it with every vertex of G). Using the same techniques, we also obtain an optimal χ‐binding function for P₅, C₄‐free graphs which is an improvement over that given in [J. L. Fouquet, V. Giakoumakis, F. Maire, and H. Thuillier, 11 , Discrete Math, 146, 33–44.]. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 293–306, 2007     

On Schur σ—Groups

In this paper, we consider some conditions of finiteness related to the p-class field tower problem over an imaginary quadratic field, where p is an odd prime.     

σ‐short Boolean algebras

We introduce properties of Boolean algebras which are closely related to the existence of winning strategies in the Banach‐Mazur Boolean game. A σ‐short Boolean algebra is a Boolean algebra that has a dense subset in which every strictly descending sequence of length ω does not have a nonzero lower bound. We give a characterization of σ‐short Boolean algebras and study properties of σ‐short Boolean algebras. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

ω‐saturated quasi‐minimal models of Th(ℚω, +, σ, 0)

We show that (ℚ^ω, +, σ, 0) is a quasi-minimal torsion-free divisible abelian group. After discussing the axiomatization of the theory of this structure, we present its ω-saturated quasi-minimal model. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

α-Stable characterization of Banach spaces (1 < α < 2)

This work characterizes some subclasses of α-stable (0 < α < 1) Banach spaces in terms of the extendibility to Radon laws of certain α-stable cylinder measures. These result extend the work of S. Chobanian and V. Tarieladze (J. Multivar. Anal.7, 183–203 (1977)). For these spaces it is shown that every Radon stable measure is the continuous image of a stable measure on a suitable L_β space with β = α(1 − α)⁻¹. The latter result extends some work of Garling (Ann. Probab.4, 600–611 (1976)) and Jain (Proceedings, Symposia in Pure Math. XXXI, p. 55–65, Amer. Math. Soc., Providence, R.I.).     

Claw‐Free Graphs,Skeletal Graphs,and a Stronger Conjecture on ω, Δ, and χ

The second author's (B.A.R.) ω, Δ, χ conjecture proposes that every graph satisfies . In this article, we prove that the conjecture holds for all claw‐free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way, we discuss a stronger local conjecture, and prove that it holds for claw‐free graphs with a three‐colorable complement. To prove our results, we introduce a very useful χ‐preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so‐called skeletal graphs.     

Random packing by ρ-connected ρ-regular graphs

A graph G is packable by the graph F if its edges can be partitioned into copies of F. If deleting the edges of any F-packable subgraph from G leaves an F-packable graph, then G is randomly F-packable. If G is F-packable but not randomly F-packable then G is F-forbidden. The minimal F-forbidden graphs provide a characterization of randomly F-packable graphs. We show that for each ρ-connected ρ-regular graph F with ρ > 1, there is a set (F) of minimal F-forbidden graphs of a simple form, such that any other minimal F-forbidden graph can be obtained from a graph in (F) by a process of identifying vertices and removing copies of F. When F is a connected strongly edge-transitive graph having more than one edge (such as a cycle or hypercube), there is only one graph in (F).     

σ‐algebras for quasirandom hypergraphs

We examine the correspondence between the various notions of quasirandomness for k‐uniform hypergraphs and σ‐algebras related to measurable hypergraphs. This gives a uniform formulation of most of the notions of quasirandomness for dense hypergraphs which have been studied, with each notion of quasirandomness corresponding to a σ‐algebra defined by a collection of subsets of . We associate each notion of quasirandomness with a collection of hypergraphs, the ‐adapted hypergraphs, so that G is quasirandom exactly when it contains roughly the correct number of copies of each ‐adapted hypergraph. We then identify, for each , a particular ‐adapted hypergraph with the property that if G contains roughly the correct number of copies of then G is quasirandom in the sense of . This generalizes recent results of Kohayakawa, Nagle, Rödl, and Schacht; Conlon, Hàn, Person, and Schacht; and Lenz and Mubayi giving this result for some particular notions of quasirandomness. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 114–139, 2017     

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     

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.