A lower bound for the recognition of digraph properties

The complexity of a digraph property is the number of entries of the adjacency matrix which must be examined by a decision tree algorithm to recognize the property in the worst case, Aanderaa and Rosenberg conjectured that there is a constant such that every digraph property which is monotone (not destroyed by the deletion of edges) and nontrivial (holds for some but not all digraphs) has complexity at leastv ² wherev is the number of nodes in the digraph. This conjecture was proved by Rivest and Vuillemin and a lower bound ofv ²/4–o(v ²) was subsequently found by Kahn, Saks, and Sturtevant. Here we show a lower bound ofv ²/2–o(v ²). We also prove that a certain class of monotone, nontrivial bipartite digraph properties is evasive (requires that every entry in the adjacency matrix be examined in the worst case).     

Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs

Equistable graphs are graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight 1. Strongly equistable graphs are graphs such that for every and every nonempty subset T of vertices that is not a maximal stable set, there exist positive vertex weights assigning weight 1 to every maximal stable set such that the total weight of T does not equal c . General partition graphs are the intersection graphs of set systems over a finite ground set U such that every maximal stable set of the graph corresponds to a partition of U . General partition graphs are exactly the graphs every edge of which is contained in a strong clique. In 1994, Mahadev, Peled, and Sun proved that every strongly equistable graph is equistable, and conjectured that the converse holds as well. In 2009, Orlin proved that every general partition graph is equistable, and conjectured that the converse holds as well. Orlin's conjecture, if true, would imply the conjecture due to Mahadev, Peled, and Sun. An “intermediate” conjecture, posed by Miklavi? and Milani? in 2011, states that every equistable graph has a strong clique. The above conjectures have been verified for several graph classes. We introduce the notion of equistarable graphs and based on it construct counterexamples to all three conjectures within the class of complements of line graphs of triangle‐free graphs. We also show that not all strongly equistable graphs are general partition.     

On Bipartite Graphs with Linear Ramsey Numbers

Dedicated to the memory of Paul Erdős We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1. Received December 1, 1999 RID="*" ID="*" Supported by NSF grant DMS-9704114 RID="**" ID="**" Supported by KBN grant 2 P03A 032 16     

Unoriented Laplacian maximizing graphs are degree maximal

A connected graph is said to be unoriented Laplacian maximizing if the spectral radius of its unoriented Laplacian matrix attains the maximum among all connected graphs with the same number of vertices and the same number of edges. A graph is said to be threshold (maximal) if its degree sequence is not majorized by the degree sequence of any other graph (and, in addition, the graph is connected). It is proved that an unoriented Laplacian maximizing graph is maximal and also that there are precisely two unoriented Laplacian maximizing graphs of a given order and with nullity 3. Our treatment depends on the following known characterization: a graph G is threshold (maximal) if and only if for every pair of vertices u,v of G, the sets N(u)?{v},N(v)?{u}, where N(u) denotes the neighbor set of u in G, are comparable with respect to the inclusion relation (and, in addition, the graph is connected). A conjecture about graphs that maximize the unoriented Laplacian matrix among all graphs with the same number of vertices and the same number of edges is also posed.     

Graham’s pebbling conjecture on product of complete bipartite graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Graham conjectured that for any connected graphs G and H, f( G x H) ⩽ f( G) f( H). We show that Graham’s conjecture holds true of a complete bipartite graph by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are complete bipartite graphs.     

Small Edge Sets Meeting all Triangles of a Graph

It was conjectured in 1981 by the third author that if a graph G does not contain more than t pairwise edge-disjoint triangles, then there exists a set of at most 2t edges that shares an edge with each triangle of G. In this paper, we prove this conjecture for odd-wheel-free graphs and for ‘triangle-3-colorable’ graphs, where the latter property means that the edges of the graph can be colored with three colors in such a way that each triangle receives three distinct colors on its edges. Among the consequences we obtain that the conjecture holds for every graph with chromatic number at most four. Also, two subclasses of K ₄-free graphs are identified, in which the maximum number of pairwise edge-disjoint triangles is equal to the minimum number of edges covering all triangles. In addition, we prove that the recognition problem of triangle-3-colorable graphs is intractable.     

How Many Ways Can One Draw A Graph?

Using results from extremal graph theory, we determine the asymptotic number of string graphs with n vertices, i.e., graphs that can be obtained as the intersection graph of a system of continuous arcs in the plane. The number becomes much smaller, for any fixed d, if we restrict our attention to systems of arcs, any two of which cross at most d times. As an application, we estimate the number of different drawings of the complete graph K_n with n vertices under various side conditions. Dedicated to Miklós Simonovits on his sixtieth birthday * Supported by NSF grant CR-00-98246, PSC-CUNY Research Award 62450-0031 and OTKA-T-032452. † Supported by OTKA-T-032452 and OTKA-T-038397.     

List Coloring of Random and Pseudo-Random Graphs

choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). It is shown that the choice number of the random graph G(n, p(n)) is almost surely whenever . A related result for pseudo-random graphs is proved as well. By a special case of this result, the choice number (as well as the chromatic number) of any graph on n vertices with minimum degree at least in which no two distinct vertices have more than common neighbors is at most . Received: October 13, 1997     

On the elusiveness of Hamiltonian property

1. IntroductionA gash G is an ordered pair of disjoillt sets (V, E) such that E is a subset of the setof unordered pairs of V, where the sets V and E are finite. The set V is cajled the setof venices and E is called the set of edges. They are usually denoted by V(G) and E(C),respectively. An edge (x, y) is said to join the venices x and y, and is sometimes denotedby xo or ear. By our definition, a graph does not colltain any loOP, neither does it colltainmultiple edges.Other terms undef…     

Graphs drawn with few crossings per edge

We show that if a graph ofv vertices can be drawn in the plane so that every edge crosses at mostk>0 others, then its number of edges cannot exceed 4.108kv. Fork4, we establish a better bound, (k+3)(v–2), which is tight fork=1 and 2. We apply these estimates to improve a result of Ajtai et al. and Leighton, providing a general lower bound for the crossing number of a graph in terms of its number of vertices and edges.Supported by NSF grant CCR-94-24398 and PSC-CUNY Research Award 667339.Supported by OTKA-T-020914, OTKA-F-22234 and the Margaret and Herman Sokol Postdoctoral Fellowship Award.     

Large regular graphs with no induced 2K 2

Letr be a positive integer. Considerr-regular graphs in which no induced subgraph on four vertices is an independent pair of edges. The numberv of vertices in such a graph does not exceed 5r/2; this proves a conjecture of Bermond. More generally, it is conjectured that ifv>2r, then the ratiov/r must be a rational number of the form 2+1/(2k). This is proved forv/r≥21/10. The extremal graphs and many other classes of these graphs are described and characterized. Research supported in part by the National Science Foundation under ISP 80110451. Research supported in part by the National Science Foundation under DMS-8401281. Research supported in part by the National Science Foundation under DMS-8504322, and by the Office of Naval Research under N00014-85K0570.     

The intrinsic dimensionality of graphs

We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich [Combinatorica, 1995]. For a graph G, let dim(G) be the smallest d such that G occurs as a (not necessarily induced) subgraph of ℤ_∞ ^d , the infinite graph with vertex set ℤ ^d and an edge (u, v) whenever ∥u − v∥_∞ = 1. The growth rate of G, denoted ρ _G , is the minimum ρ such that every ball of radius r > 1 in G contains at most r ^ρ vertices. By simple volume arguments, dim(G) = Ω(ρ _G ). Levin conjectured that this lower bound is tight, i.e., that dim(G) = O(ρ _G ) for every graph G. Previously, it was unknown whether dim(G) could be bounded above by any function of ρ _G . We show that a weaker form of Levin’s conjecture holds by proving that dim(G) = O(ρ _G log ρ _G ) for any graph G. We disprove, however, the specific bound of the conjecture and show that our upper bound is tight by exhibiting graphs for which dim(G) = Ω(ρ _G log ρ _G ). For several special families of graphs (e.g., planar graphs), we salvage the strong form, showing that dim(G) = O(ρ _G ). Our results extend to a variant of the conjecture for finite-dimensional Euclidean spaces posed by Linial and independently by Benjamini and Schramm. Supported by NSF grant CCR-0121555 and by an NSF Graduate Research Fellowship.     

The competition number of a graph and the dimension of its hole space

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of the important research problems in the study of competition graphs to characterize a graph by its competition number. Recently, the relationship between the competition number and the number of holes of a graph has been studied. A hole of a graph is a cycle of length at least 4 as an induced subgraph. In this paper, we conjecture that the dimension of the hole space of a graph is not smaller than the competition number of the graph. We verify this conjecture for various kinds of graphs and show that our conjectured inequality is indeed an equality for connected triangle-free graphs.     

On the conjecture of hajós

Hajós conjectured that everys-chromatic graph contains a subdivision ofK _s, the complete graph ons vertices. Catlin disproved this conjecture. We prove that almost all graphs are counter-examles in a very strong sense.     

Orientations of graphs with uncountable chromatic number

Motivated by an old conjecture of P. Erdős and V. Neumann‐Lara, our aim is to investigate digraphs with uncountable dichromatic number and orientations of undirected graphs with uncountable chromatic number. A graph has uncountable chromatic number if its vertices cannot be covered by countably many independent sets, and a digraph has uncountable dichromatic number if its vertices cannot be covered by countably many acyclic sets. We prove that, consistently, there are digraphs with uncountable dichromatic number and arbitrarily large digirth; this is in surprising contrast with the undirected case: any graph with uncountable chromatic number contains a 4‐cycle. Next, we prove that several well‐known graphs (uncountable complete graphs, certain comparability graphs, and shift graphs) admit orientations with uncountable dichromatic number in ZFC. However, we show that the statement “every graph G of size and chromatic number ω₁ has an orientation D with uncountable dichromatic number” is independent of ZFC. We end the article with several open problems.     

On Connected [g,f +1]-Factors in Graphs

Let G = (V (G),E(G)) be a graph with vertex set V (G) and edge set E(G), and g and f two positive integral functions from V (G) to Z⁺-{1} such that g(v) ≤ f(v) ≤ d_G(v) for all v ∈V (G), where d_G(v) is the degree of the vertex v. It is shown that every graph G, including both a [g,f]-factor and a hamiltonian path, contains a connected [g,f +1]-factor. This result also extends Kano’s conjecture concerning the existence of connected [k,k+1]-factors in graphs. * The work of this author was supported by NSFC of China under Grant No. 10271065, No. 60373025. † The work of these authors was also supported in part by the US Department of Energy’s Genomes to Life program (http://doegenomestolife.org/) under project, “Carbon Sequestration in Synechococcus sp.: From Molecular Machines to Hierarchical Modeling” (www.genomes2life.org) and by National Science Foundation (NSF/DBI-0354771,NSF/ITR-IIS-0407204).     

On the addressing problem for directed graphs

The “distance” from vertexu to vertexv in a strongly connected digraph is the number of arcs in a shortest directed path fromu tov. The addressing problem, first formulated in the undirected case by Graham and Pollak, entails the assignment of a string of symbols to each vertex in such a way that the distances between vertices are equal to modified Hamming distances between corresponding strings. A scheme for addressing digraphs is proposed, and the minimum address length is studied both in general and in certain special cases. The problem has some interesting reformulations in terms of matrix factorization and extremal set theory. Supported by NSF grant MCS 84-02054.     

Ramsey-type Theorems with Forbidden Subgraphs

Dedicated to the memory of Paul Erdős   A graph is called H-free if it contains no induced copy of H. We discuss the following question raised by Erdős and Hajnal. Is it true that for every graph H, there exists an such that any H-free graph with n vertices contains either a complete or an empty subgraph of size at least ? We answer this question in the affirmative for a special class of graphs, and give an equivalent reformulation for tournaments. In order to prove the equivalence, we establish several Ramsey type results for tournaments. Received August 22, 1999 RID="*" ID="*" Supported by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. RID="†" ID="†" Supported by NSF grant CR-9732101, PSC-CUNY Research Award 663472, and OTKA-T-020914. RID="‡" ID="‡" Supported by TKI grant Stochastics@TUB, and OTKA-T-026203.     

The gallai-younger conjecture for planar graphs

Younger conjectured that for everyk there is ag(k) such that any digraphG withoutk vertex disjoint cycles contains a setX of at mostg(k) vertices such thatG–X has no directed cycles. Gallai had previously conjectured this result fork=1. We prove this conjecture for planar digraphs. Specifically, we show that ifG is a planar digraph withoutk vertex disjoint directed cycles, thenG contains a set of at mostO(klog(k)log(log(k))) vertices whose removal leaves an acyclic digraph. The work also suggests a conjecture concerning an extension of Vizing's Theorem for planar graphs.     

On kernels in perfect graphs

A kernel of a digraphD is a set of vertices which is both independent and absorbant. In 1983, C. Berge and P. Duchet conjectured that an undirected graphG is perfect if and only if the following condition is fulfilled: ifD is an orientation ofG (where pairs of opposite arcs are allowed) and if every clique ofD has a kernel thenD has a kernel. We prove here the conjecture for the complements of strongly perfect graphs and establish that a minimal counterexample to the conjecture is not a complete join of an independent set with another graph.