The Chromatic Spectrum of Mixed Hypergraphs

 A mixed hypergraph is a triple ℋ=(X, ?, ?), where X is the vertex set, and each of ?, ? is a list of subsets of X. A strict k-coloring of ℋ is a surjection c:X→{1,…,k} such that each member of ? has two vertices assigned a common value and each member of ? has two vertices assigned distinct values. The feasible set of H is {k: H has a strict k-coloring}. Among other results, we prove that a finite set of positive integers is the feasible set of some mixed hypergraph if and only if it omits the number 1 or is an interval starting with 1. For the set {s,t} with 2≤s≤t−2, the smallest realization has 2t−s vertices. When every member of ?∪? is a single interval in an underlying linear order on the vertices, the feasible set is also a single interval of integers. Received: May 24, 1999 Final version received: August 31, 2000     

The cover pebbling number of graphs

A pebbling move on a graph consists of taking two pebbles off of one vertex and placing one pebble on an adjacent vertex. In the traditional pebbling problem we try to reach a specified vertex of the graph by a sequence of pebbling moves. In this paper we investigate the case when every vertex of the graph must end up with at least one pebble after a series of pebbling moves. The cover pebbling number of a graph is the minimum number of pebbles such that however the pebbles are initially placed on the vertices of the graph we can eventually put a pebble on every vertex simultaneously. We find the cover pebbling numbers of trees and some other graphs. We also consider the more general problem where (possibly different) given numbers of pebbles are required for the vertices.     

Induced Decompositions of Highly Dense Graphs

Given two graphs F and G, an induced F‐decomposition of G is a partition of into induced subgraphs isomorphic to F. Bondy and Szwarcfiter [J. Graph Theory, DOI: 10.1002/jgt.21654] defined the value as the maximum number of edges in a graph of order n admitting an induced F‐decomposition and determined the value of for some graphs (and families of graphs). In this article, we prove that is valid for all graphs F. We also present tighter asymptotic bounds for some of the small graphs for which the exact value of remains unknown. The proofs are based on the heavy use of various classes of Kneser graphs and hypergraphs.     

Hydration Dynamics and the Future of Small-Amplitude AFM Imaging in Air

Here, we discuss the effects that the dynamics of the hydration layer and other variables, such as the tip radius, have on the availability of imaging regimes in dynamic AFM—including multifrequency AFM. Since small amplitudes are required for high-resolution imaging, we focus on these cases. It is possible to fully immerse a sharp tip under the hydration layer and image with amplitudes similar to or smaller than the height of the hydration layer, i.e., ~1 nm. When mica or HOPG surfaces are only cleaved, molecules adhere to their surfaces, and reaching a thermodynamically stable state for imaging might take hours. During these first hours, different possibilities for imaging emerge and change, implying that these conditions must be considered and reported when imaging.     

Brooks-type theorems for choosability with separation

We consider the following type of problems. Given a graph G = (V, E) and lists L(v) of allowed colors for its vertices v ∈ V such that |L(v)| = p for all v ∈ V and |L(u) ∩ L(v)| ≤ c for all uv ∈ E, is it possible to find a “list coloring,” i.e., a color f(v) ∈ L(v) for each v ∈ V, so that f(u) ≠ f(v) for all uv ∈ E? We prove that every of maximum degree Δ admits a list coloring for every such list assignment, provided p ≥ . Apart from a multiplicative constant, the result is tight, as lists of length may be necessary. Moreover, for G = K_n (the complete graph on n vertices) and c = 1 (i.e., almost disjoint lists), the smallest value of p is shown to have asymptotics (1 + o(1)) . For planar graphs and c = 1, lists of length 4 suffice. ˜© 1998 John Wiley & Sons, Inc. J Graph Theory 27: 43–49, 1998     

Cycles of given color patterns

In 2-edge-colored graphs, we define an (s, t)-cycle to be a cyle of length s + t, in which s consecutive edges are in one color and the remaining t edges are in the other color. Here we investigate the existence of (s, t)-cycles, in a 2-edge-colored complete graph K^c_n on n vertices. In particular, in the first result we give a complete characterization for the existence of (s, t)-cycles in K^c_n with n relatively large with respect to max({s, t}). We also study cycles of length 4 for all possible values of s and t. Then, we show that K^c_n contains an (s, t)-hamiltonian cycle unless it is isomorphic to a specified graph. This extends a result of A. Gyárfás [Journal of Graph Theory, 7 (1983), 131–135]. Finally, we give some sufficient conditions for the existence of (s, 1)-cycles, (inverted sans serif aye) s ϵ {2, 3,…, n − 2}. © 1996 John Wiley & Sons, Inc.     

Covering of graphs by complete bipartite subgraphs; Complexity of 0–1 matrices

We prove that the edge set of an arbitrary simple graphG onn vertices can be covered by at mostn−[log₂ n]+1 complete bipartite subgraphs ofG. If the weight of a subgraph is the number of its vertices, then there always exists a cover with total weightc(n ²/logn) and this bound is sharp apart from a constant factor. Our result answers a problem of T. G. Tarján. Dedicated to Paul Erdős on his seventieth birthday     

On color critical graphs

It is shown that the minimal number of edges which have to be omitted from a (k + 1)-critical graph on n vertices in order to make it bipartite is at least ^k₂ for n large enough. This bound is best possible. Various related questions are considered.     

Maximum bipartite subgraphs of Kneser graphs

We investigate the maximum number of edges in a bipartite subgraph of the Kneser graphK(n, r). The exact solution is given for eitherr arbitrary andn (4.3 + o(1))r, orr = 2 andn arbitrary. The problem is in connection with the study of the bipartite subgraph polytope of a graph.Research supported in part by the AKA Research Fund of the Hungarian Academy of Sciences     

Zero-sum block designs and graph labelings

Proving a conjecture of Aigner and Triesch, we show that every graph G = (V,E) without isolated vertices and isolated edges admits an edge labeling ξ: E → {0,1}^m with binary vectors of length m = [log₂ n] + 1 such that the sums. CALLING STATEMENT : (taken modulo 2 componentwise) are mutually distinct, provided that n is sufficiently large. The proof combines probabilistic arguments with explicitly constructed Steiner systems. © 1995 John Wiley & Sons, Inc.