Independent sets ink-chromatic graphs

A graph is said to have propertyP _k if in eachk-colouring ofG using allk colours there arek independent vertices having all colours. An (unpublished) suggestion of P. Erdős is answered in the affirmative: For eachk≧3 there is a k-critical graph withP _k . With the aid of a construction of T. Gallaik-chromatic graphs (k≧7) withP _k orP _k+1 of arbitrarily high connectivity are obtained. The main result is: Eachk-chromatic graph (k≧3) of girth ≧6 hasP _k or is a circuit of length 7. Dedicated to Paul Erdős on his seventieth birthday     

Independent sets in regular graphs

Lower and upper bounds for the maximal number of independent vertices in a regular graph are obtained, it is shown that the bounds are best possible. Some properties of regular graphs concerning the property ℋ defined below are investigated. This paper is to be a part of the author’s Ph. D. thesis written under the supervision of Prof. B. Grünbaum at the Hebrew University of Jerusalem.     

Spanning trees with many leaves in cubic graphs

For a connected graph G let L(G) denote the maximum number of leaves in any spanning tree of G. We give a simple construction and a complete proof of a result of Storer that if G is a connected cubic graph on n vertices, then L(G) ? [(n/4) + 2], and this is best possible for all (even) n. The main idea is to count the number of “dead leaves” as the tree is being constructed. This method of amortized analysis is used to prove the new result that if G is also 3-connected, then L(G) ? [(n/3) + (4/3)], which is best possible for many n. This bound holds more generally for any connected cubic graph that contains no subgraph K₄ - e. The proof is rather elaborate since several reducible configurations need to be eliminated before proceeding with the many tricky cases in the construction.     

Independent sets,cliques and hamiltonian graphs

LetG be ak-connected (k 2) graph onn vertices. LetS be an independent set ofG. S is called essential if there exist two distinct vertices inS which have a common neighbor inG. LetV _r, be a clique which is a complete subgraph ofG. In this paper it is proven that if every essential independent setS ofk + 1 vertices satisfiesS V _r , thenG is hamiltonian, orG{u} is hamiltonian for someu V _r, orG is one of three classes of exceptional graphs. Our theorem generalizes several well-known theorems.     

Intersection graphs of proper subtrees of unicyclic graphs

A graph is fraternally oriented iff for every three vertices u, ν, w the existence of the edges u → w and ν → w implies that u and ν are adjacent. A directed unicyclic graph is obtained from a unicyclic graph by orienting the unique cycle clockwise and by orienting the appended subtrees from the cycle outwardly. Two directed subtrees s, t of a directed unicyclic graph are proper if their union contains no (directed or undirected) cycle and either they are disjoint or one of them s has its root r(s) in t and contains all the successors of r(s) in t. In the present paper we prove that G is an intersection graph of a family of proper directed subtrees of a directed unicyclic graph iff it has a fraternal orientation such that for every vertex ν, G(Γⁱⁿν) is acyclic and G(Γ^outν) is the transitive closure of a tree. We describe efficient algorithms for recognizing when such graphs are perfect and for testing isomorphism of proper circular-arc graphs.     

Chromatic number and subtrees of graphs

Let G and H be two graphs. We say that G induces H if G has an induced subgraph isomorphic to H: A. Gyárfás and D. Sumner, independently, conjectured that, for every tree T. there exists a function f _T ; called binding function, depending only on T with the property that every graph G with chromatic number f _T (ω(G)) induces T. A. Gyárfás, E. Szemerédi and Z. Tuza confirmed the conjecture for all trees of radius two on triangle-free graphs, and H. Kierstead and S. Penrice generalized the approach and the conclusion of A. Gyárfás et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(14 ^r-1(r - 1)!) times. We extend the approach of A. Gyárfás and present a binding function for trees obtained by identifying one end of a path and the center of a star. We also improve A. Scott's upper bound by modifying his subtree structure and partition technique, and show that for every integer k and every tree T of radius r, every graph with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(6 ^r?2) times.     

Induced subtrees in graphs of large chromatic number

Our paper proves special cases of the following conjecture: for any fixed tree T there exists a natural number f = f (T) to that every triangle-free graph of chromaticnumber f(T) contains T as an induced subgraph. The main result concerns the case when T has radius two.     

Independent sets in the graphs with bounded minors of the extended incidence matrix

We characterize the graphs with the absolute values of minors of the extended incidence matrix bounded above by some constant. We prove that, for every fixed k, the independent set problem is solvable in polynomial time for the graphs with the absolute value at most k of every minor of the matrix obtained from the incidence matrix by appending a column of 1s.     

The intersection graphs of subtrees in trees are exactly the chordal graphs

The intersection graph of a family of subtrees in an undirected tree is called a subtree graph. A graph is called chordal if every simple circuit with more than three vertices has an edge connecting two non-consecutive vertices. In this paper, we prove that, for a graph G, the following conditions are equivalent: (i) G is a chordal graph; (ii) G is a subtree graph; (iii) G is a proper subtree graph.Consider a chordal graph G. We give an efficient algorithm for constructing a representation of G by a family of subtrees in a tree.     

Independent sets in regular graphs and sum-free subsets of finite groups

It is shown that there exists a function∈(k) which tends to 0 ask tends to infinity, such that anyk-regular graph onn vertices contains at most 2^{(1/2+∈(k))n} independent sets. This settles a conjecture of A. Granville and has several applications in Combinatorial Group Theory. Research supported in part by the United States-Israel Binational Science Foundation and by a Bergmann Memorial Grant.     

On the number of subtrees for almost all graphs

In this article it is shown that the number of common edges of two random subtrees of K_n having r and s vertices, respectively, has a Poisson distribution with expectation 2λμ if $\mathop {\lim }\limits_{n \to \infty } r/n = \lambda$ and $\mathop {\lim }\limits_{n \to \infty } s/n = \mu$. Also, some estimations of the number of subtrees for almost all graphs are made by using Chebycheff's inequality. © 1994 John Wiley & Sons, Inc.     

Spanning trees with many leaves

Let a maximal chain of vertices of degree 2 in a graph G consist of k > 0 vertices. We prove that G has a spanning tree with more than \fracv(G)2k + 4 \frac{{v(G)}}{{2k + 4}} leaves (where υ(G) is the number of vertices of the graph G). We present an infinite series of examples showing that the constant \frac12k + 4 \frac{1}{{2k + 4}} cannot be enlarged. Bibliography: 7 titles.     

Constant tolerance intersection graphs of subtrees of a tree

A chordal graph is the intersection graph of a family of subtrees of a host tree. In this paper we generalize this. A graph G=(V,E) has an (h,s,t)-representation if there exists a host tree T of maximum degree at most h, and a family of subtrees {S_v}_v∈V of T, all of maximum degree at most s, such that uv∈E if and only if |S_u∩S_v|?t. For given h,s, and t, there exist infinitely many forbidden induced subgraphs for the class of (h,s,t)-graphs. On the other hand, for fixed h?s?3, every graph is an (h,s,t)-graph provided that we take t large enough. Under certain conditions representations of larger graphs can be obtained from those of smaller ones by amalgamation procedures. Other representability and non-representability results are presented as well.     

Embedding finite graphs into graphs colored with infinitely many colors

We prove that for any cardinalτ and for any finite graphH there is a graphG such that for any coloring of the pairs of vertices ofG withτ colors there is always a copy ofH which is an induced subgraph ofG so that both the edges of the copy and the edges of the complement of the copy are monochromatic. Research supported by Hungarian National Science Foundation OTKA grant 1805.