On the stability number of AH-free graphs

We describe a new class of graphs for which the stability number can be obtained in polynomial time. The algorithm is based on an iterative procedure that, at each step, builds from a graph G a new graph G^l that has fewer nodes and has the property that α(G^l) = α(G) ? 1. This new class of graphs is different from the known classes for which the stability number can be computed in polynomial time. © 1993 John Wiley & Sons, Inc.     

Interval Routing onk-Trees

A graph has an optimall-interval routing scheme if it is possible to direct messages along shortest paths by labeling each edge with at mostlpairwise-disjoint subintervals of the cyclic interval [1…n] (where each node of the graph is labeled by an integer in the range). Although much progress has been made forl = 1, there is as yet no general tight characterization of the classes of graphs associated with largerl. Bodlaenderet al. have shown that under the assumption of dynamic cost links, each graph with an optimall-interval routing scheme has treewidth of at most 4l. For the setting without dynamic cost links, this paper addresses the complementary question of the number of intervals required to label classes of graphs of treewidthk. Although it has been shown that there exist graphs of treewidth 2 that require a nonconstant number of intervals, our work demonstrates a class of graphs of treewidth 2, namely 2-trees, that are guaranteed to allow 3-interval routing schemes. In contrast, this paper presents a 2-tree that cannot have a 2-interval routing scheme. For generalk, anyk-tree is shown to have an optimal interval routing scheme using 2^{k + 1}intervals per edge.     

A note on the bichromatic numbers of graphs

For a pair of integers k, l≥0, a graph G is (k, l)‐colorable if its vertices can be partitioned into at most k independent sets and at most l cliques. The bichromatic number χ^b(G) of G is the least integer r such that for all k, l with k+l=r, G is (k, l)‐colorable. The concept of bichromatic numbers simultaneously generalizes the chromatic number χ(G) and the clique covering number θ(G), and is important in studying the speed of hereditary properties and edit distances of graphs. It is easy to see that for every graph G the bichromatic number χ^b(G) is bounded above by χ(G)+θ(G)?1. In this article, we characterize all graphs G for which the upper bound is attained, i.e., χ^b(G)=χ(G)+θ(G)?1. It turns out that all these graphs are cographs and in fact they are the critical graphs with respect to the (k, l)‐colorability of cographs. More specifically, we show that a cograph H is not (k, l)‐colorable if and only if H contains an induced subgraph G with χ(G)=k+1, θ(G)=l+1 and χ^b(G)=k+l+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 263–269, 2010     

An extremal problem for paths in bipartite graphs

A formula is found for the maximum number of edges in a graph G ? K(a, b) which contains no path P_2l for l > c. A similar formula is found for the maximum number of edges in G ? K(a, b) containing no P_{2l + 1} for l > c. In addition, all extremal graphs are determined.     

Random I-colorable graphs

In this article we investigate properties of the class of all l-colorable graphs on n vertices, where l = l(n) may depend on n. Let G^l_n denote a uniformly chosen element of this class, i.e., a random l-colorable graph. For a random graph G^l_n we study in particular the property of being uniquely l-colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l-colorable graphs on n vertices with m = m(n) edges.     

Minimally (k,k)‐edge‐connected graphs

For an integer l > 1, the l‐edge‐connectivity of a connected graph with at least l vertices is the smallest number of edges whose removal results in a graph with l components. A connected graph G is (k, l)‐edge‐connected if the l‐edge‐connectivity of G is at least k. In this paper, we present a structural characterization of minimally (k, k)‐edge‐connected graphs. As a result, former characterizations of minimally (2, 2)‐edge‐connected graphs in [J of Graph Theory 3 (1979), 15–22] are extended. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 116–131, 2003     

On the number of sparse connected graphs

We present a short way of estimating the number of connected graphs with k vertices k + l edges, when k→∞, l = l(k)→∞ but l = o(k).     

Counting connected graphs asymptotically

We find the asymptotic number of connected graphs with k vertices and k−1+l edges when k,l approach infinity, re-proving a result of Bender, Canfield and McKay. We use the probabilistic method, analyzing breadth-first search on the random graph G(k,p) for an appropriate edge probability p. Central is the analysis of a random walk with fixed beginning and end which is tilted to the left.     

Strong chromatic index of subset graphs

The strong chromatic index of a graph G, denoted sq(G), is the minimum number of parts needed to partition the edges of G into induced matchings. For 0 ≤ k ≤ l ≤ m, the subset graph S_m(k, l) is a bipartite graph whose vertices are the k- and l-subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. We show that and that this number satisfies the strong chromatic index conjecture by Brualdi and Quinn for bipartite graphs. Further, we demonstrate that the conjecture is also valid for a more general family of bipartite graphs. © 1997 John Wiley & Sons, Inc.     

Quasi‐random hypergraphs revisited

The quasi‐random theory for graphs mainly focuses on a large equivalent class of graph properties each of which can be used as a certificate for randomness. For k ‐graphs (i.e., k ‐uniform hypergraphs), an analogous quasi‐random class contains various equivalent graph properties including the k ‐discrepancy property (bounding the number of edges in the generalized induced subgraph determined by any given (k ‐ 1) ‐graph on the same vertex set) as well as the k ‐deviation property (bounding the occurrences of “octahedron”, a generalization of 4 ‐cycle). In a 1990 paper (Chung, Random Struct Algorithms 1 (1990) 363‐382), a weaker notion of l ‐discrepancy properties for k ‐graphs was introduced for forming a nested chain of quasi‐random classes, but the proof for showing the equivalence of l ‐discrepancy and l ‐deviation, for 2 ≤ l < k, contains an error. An additional parameter is needed in the definition of discrepancy, because of the rich and complex structure in hypergraphs. In this note, we introduce the notion of (l,s) ‐discrepancy for k ‐graphs and prove that the equivalence of the (k,s) ‐discrepancy and the s ‐deviation for 1 ≤ s ≤ k. We remark that this refined notion of discrepancy seems to point to a lattice structure in relating various quasi‐random classes for hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Probabilities of Sentences about Very Sparse Random Graphs

We consider random graphs with edge probability βn^?α, where n is the number of vertices of the graph, β > 0 is fixed, and α = 1 or α = (l + 1) /l for some fixed positive integer l. We prove that for every first-order sentence, the probability that the sentence is true for the random graph has an asymptotic limit.     

Circular choosability of graphs

This paper discusses the circular version of list coloring of graphs. We give two definitions of the circular list chromatic number (or circular choosability) χ_{c, l}(G) of a graph G and prove that they are equivalent. Then we prove that for any graph G, χ_{c, l}(G) ≥ χ_l(G) ? 1. Examples are given to show that this bound is sharp in the sense that for any ? 0, there is a graph G with χ_{c, l}(G) > χ_l(G) ? 1 + ?. It is also proved that k‐degenerate graphs G have χ_{c, l}(G) ≤ 2k. This bound is also sharp: for each ? < 0, there is a k‐degenerate graph G with χ_{c, l}(G) ≥ 2k ? ?. This shows that χ_{c, l}(G) could be arbitrarily larger than χ_l(G). Finally we prove that if G has maximum degree k, then χ_{c, l}(G) ≤ k + 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 210–218, 2005     

Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size

Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are nonnegative integers. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such an “almost uniform” partition is called an (l,u)-partition. We deal with three problems to find an (l,u)-partition of a given graph; the minimum partition problem is to find an (l,u)-partition with the minimum number of components; the maximum partition problem is defined analogously; and the p-partition problem is to find an (l,u)-partition with a fixed number p of components. All these problems are NP-complete or NP-hard, respectively, even for series-parallel graphs. In this paper we show that both the minimum partition problem and the maximum partition problem can be solved in time O(u⁴n) and the p-partition problem can be solved in time O(p²u⁴n) for any series-parallel graph with n vertices. The algorithms can be extended for partial k-trees, that is, graphs with bounded tree-width.     

Nash inequalities for finite Markov chains

This paper develops bounds on the rate of decay of powers of Markov kernels on finite state spaces. These are combined with eigenvalue estimates to give good bounds on the rate of convergence to stationarity for finite Markov chains whose underlying graph has moderate volume growth. Roughly, for such chains, order (diameter) steps are necessary and suffice to reach stationarity. We consider local Poincaré inequalities and use them to prove Nash inequalities. These are bounds onl ₂-norms in terms of Dirichlet forms andl ₁-norms which yield decay rates for iterates of the kernel. This method is adapted from arguments developed by a number of authors in the context of partial differential equations and, later, in the study of random walks on infinite graphs. The main results do not require reversibility.     

Threshold functions for asymmetric Ramsey properties involving cycles

We consider the binomial random graph G_p and determine a sharp threshold function for the edge-Ramsey property for all l₁,…,l_r, where C^l denotes the cycle of length l. As deterministic consequences of our results, we prove the existence of sparse graphs having the above Ramsey property as well as the existence of infinitely many critical graphs with respect to the property above. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 245–276, 1997     

Theory of path length distributions I

The Path Length Distribution (PLD) of a (p, q) graph is defined to be the array (X₀, X₁, X₂, …, X_p-1), where X₀ is the number of (unordered) pairs of vertices which have no path connecting them and X_l, 1 ≦ l ≦ p-1, is the number of pairs of vertices which are connected by a path of length l (see [1, 2]). The topic of this paper is the occurence of non-isomorphic graphs having the same path length distribution. For trees, a constructive procedure is given, showing that for any positive integer N there exist N non-isomorphic trees of diameter four which have the same PLD. Also considered are PLD-maximal graphs — those graphs with p vertices such that all pairs of vertices are connected by a path of length l for 2 ≦ l ≦ p-1. In addition to providing more examples of non-isomorphic graphs having the same PLD, PLD-maximal graphs are of intrinsic interest. For PLD-maximal graphs, we give sufficient degree and edge conditions and a necessary edge condition.     

On the structure of graphs with a unique k‐factor

In this paper we study the structure of graphs with a unique k‐factor. Our results imply a conjecture of Hendry on the maximal number m (n,k) of edges in a graph G of order n with a unique k‐factor: For we prove and construct all corresponding extremal graphs. For we prove . For n = 2kl, l ∈ ℕ, this bound is sharp, and we prove that the corresponding extremal graph is unique up to isomorphism. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 227–243, 2000     

Leaf‐Critical and Leaf‐Stable Graphs

The minimum leaf number ml(G) of a connected graph G is defined as the minimum number of leaves of the spanning trees of G if G is not hamiltonian and 1 if G is hamiltonian. We study nonhamiltonian graphs with the property for each or for each . These graphs will be called ‐leaf‐critical and l‐leaf‐stable, respectively. It is far from obvious whether such graphs exist; for example, the existence of 3‐leaf‐critical graphs (that turn out to be the so‐called hypotraceable graphs) was an open problem until 1975. We show that l‐leaf‐stable and l‐leaf‐critical graphs exist for every integer , moreover for n sufficiently large, planar l‐leaf‐stable and l‐leaf‐critical graphs exist on n vertices. We also characterize 2‐fragments of leaf‐critical graphs generalizing a lemma of Thomassen. As an application of some of the leaf‐critical graphs constructed, we settle an open problem of Gargano et al. concerning spanning spiders. We also explore connections with a family of graphs introduced by Grünbaum in correspondence with the problem of finding graphs without concurrent longest paths.     

Graphs omitting sums of complete graphs

For every finite m and n there is a finite set {G₁, …, G_l} of countable (m · K_n)-free graphs such that every countable (m · K_n)-free graph occurs as an induced subgraph of one of the graphs G_l © 1997 John Wiley & Sons, Inc.     

Local Chromatic Number, KY Fan's Theorem, And Circular Colorings

The local chromatic number of a graph was introduced in [14]. It is in between the chromatic and fractional chromatic numbers. This motivates the study of the local chromatic number of graphs for which these quantities are far apart. Such graphs include Kneser graphs, their vertex color-critical subgraphs, the Schrijver (or stable Kneser) graphs; Mycielski graphs, and their generalizations; and Borsuk graphs. We give more or less tight bounds for the local chromatic number of many of these graphs. We use an old topological result of Ky Fan [17] which generalizes the Borsuk–Ulam theorem. It implies the existence of a multicolored copy of the complete bipartite graph K_{⌈t/2⌉,⌊t/2⌋} in every proper coloring of many graphs whose chromatic number t is determined via a topological argument. (This was in particular noted for Kneser graphs by Ky Fan [18].) This yields a lower bound of ⌈t/2⌉ + 1 for the local chromatic number of these graphs. We show this bound to be tight or almost tight in many cases. As another consequence of the above we prove that the graphs considered here have equal circular and ordinary chromatic numbers if the latter is even. This partially proves a conjecture of Johnson, Holroyd, and Stahl and was independently attained by F. Meunier [42]. We also show that odd chromatic Schrijver graphs behave differently, their circular chromatic number can be arbitrarily close to the other extreme. * Research partially supported by the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. T037846, T046376, AT048826, and NK62321. † Research partially supported by the NSERC grant 611470 and the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. T037846, T046234, AT048826, and NK62321.