On the strong perfect graph conjecture and critical graphs

In this paper we obtain some properties of graphs which are critical with respect to perfectness. Some alternate forms of Berge's [2] strong perfect graph conjecture are also given.     

Remarks on the critical graph conjecture

The vertex-critical graph conjecture (critical graph conjecture respectively) states that every vertex-critical (critical) graph has an odd number of vertices. In this note we prove that if G is a critical graph of even order, then G has at least three vertices of less-than-maximum valency. In addition, if G is a 3-critical multigraph of smallest even order, then G is simple and has no triangles.     

On the strong perfect graph conjecture

A graph G is perfect if for every induced subgraph H of G the chromatic number χ(H) equals the largest number ω(H) of pairwise adjacent vertices in H. Berge's famous Strong Perfect Graph Conjecture asserts that a graph G is perfect if and only if neither G nor its complement G¯ contains an odd chordless cycle of length at least 5. Its resolution has eluded researchers for more than 20 years. We prove that the conjecture is true for a class of graphs that we describe by forbidden configurations.     

The rise and fall of the critical graph conjecture

In this expository paper we discuss the critical graph conjecture and its eventual disproof by M.K. Goldberg and others.     

On the Hadwiger's conjecture for graph products

The Hadwiger number η(G) of a graph G is the largest integer h such that the complete graph on h nodes K_h is a minor of G. Equivalently, η(G) is the largest integer such that any graph on at most η(G) nodes is a minor of G. The Hadwiger's conjecture states that for any graph G, η(G)?χ(G), where χ(G) is the chromatic number of G. It is well-known that for any connected undirected graph G, there exists a unique prime factorization with respect to Cartesian graph products. If the unique prime factorization of G is given as G₁□G₂□?□G_k, where each G_i is prime, then we say that the product dimension of G is k. Such a factorization can be computed efficiently.In this paper, we study the Hadwiger's conjecture for graphs in terms of their prime factorization. We show that the Hadwiger's conjecture is true for a graph G if the product dimension of G is at least . In fact, it is enough for G to have a connected graph M as a minor whose product dimension is at least , for G to satisfy the Hadwiger's conjecture. We show also that if a graph G is isomorphic to F^d for some F, then η(G)?χ(G)^{⌊(d-1)/2⌋}, and thus G satisfies the Hadwiger's conjecture when d?3. For sufficiently large d, our lower bound is exponentially higher than what is implied by the Hadwiger's conjecture.Our approach also yields (almost) sharp lower bounds for the Hadwiger number of well-known graph products like d-dimensional hypercubes, Hamming graphs and the d-dimensional grids. In particular, we show that for the d-dimensional hypercube H_d, . We also derive similar bounds for G^d for almost all G with n nodes and at least edges.     

On the graph complement conjecture for minimum semidefinite rank

In this note, we combine a number of recent ideas to give new results on the graph complement conjecture for minimum semidefinite rank.     

On a conjecture concerning the orientation number of a graph

For a connected graph G containing no bridges, let D(G) be the family of strong orientations of G; and for any D∈D(G), we denote by d(D) the diameter of D. The orientation number of G is defined by . Let G(p,q;m) denote the family of simple graphs obtained from the disjoint union of two complete graphs K_p and K_q by adding m edges linking them in an arbitrary manner. The study of the orientation numbers of graphs in G(p,q;m) was introduced by Koh and Ng [K.M. Koh, K.L. Ng, The orientation number of two complete graphs with linkages, Discrete Math. 295 (2005) 91-106]. Define and . In this paper we prove a conjecture on α proposed by K.M. Koh and K.L. Ng in the above mentioned paper, for q≥p+4.     

Reductions of the graph reconstruction conjecture

In this note we shall show that the Graph Reconstruction Conjecture (also called the Kelly-Ulam conjecture [1, p. 11]) is equivalent to a conjecture about the algebraic properties of certain directed trees and their homomorphic images. We shall show the the Greph Reconstruction Conjecture is equivalent to recognizing the (abstract) group of a graph from the tree (generalized “deck”) of the graph.     

Equivalence of the strengthened Hanna Neumann conjecture and the amalgamated graph conjecture

Summary We show that Walter Neumann's strengthened form of Hanna Neumann's conjecture on the best possible upper bound for the rank of the intersection of two subgroups of a free group is equivalent to a conjecture on the best possible upper bound for the number of edges in a bipartite graph with a certain weak symmetry condition. We illustrate the usefulness of this equivalence by deriving relatively easily certain previously known results.Oblatum 30-VIII-1993     

A proof of the bounded graph conjecture

Summary An infinite graph is called bounded if for every labelling of its vertices with natural numbers there exists a sequence of natural numbers which eventually exceeds the labelling along any ray in the graph. We prove an old conjecture of Halin, which characterizes the bounded graphs in terms of four forbidden topological subgraphs.Oblatum 17-IV-1991 & 25-X-1991     

Normal hypergraphs and the perfect graph conjecture

A hypergraph is called normal if the chromatic index of any partial hypergraph H′ of it coincides with the maximum valency in H′. It is proved that a hypergraph is normal iff the maximum number of disjoint hyperedges coincides with the minimum number of vertices representing the hyperedges in each partial hypergraph of it. This theorem implies the following conjecture of Berge: The complement of a perfect graph is perfect. A new proof is given for a related theorem of Berge and Las Vergnas. Finally, the results are applied on a problem of integer valued linear programming, slightly sharpening some results of Fulkerson.     

The graph formulation of the union-closed sets conjecture

The union-closed sets conjecture asserts that in a finite non-trivial union-closed family of sets there has to be an element that belongs to at least half the sets. We show that this is equivalent to the conjecture that in a finite non-trivial graph there are two adjacent vertices each belonging to at most half of the maximal stable sets. In this graph formulation other special cases become natural. The conjecture is trivially true for non-bipartite graphs and we show that it holds also for the classes of chordal bipartite graphs, subcubic bipartite graphs, bipartite series-parallel graphs and bipartitioned circular interval graphs. We derive that the union-closed sets conjecture holds for all union-closed families being the union-closure of sets of size at most three.     

Combinatorial designs related to the strong perfect graph conjecture

When α, ω are positive integers, we set n = αω + 1 and look for zero-one matrices X, Y of size n × n such that

$\text{XY= YX = J ? I}$

,

$\text{JX = XJ = αJ}$

, JY = YJ = ωJ. Simple solutions of these matrix equations are easy to find; we describe ways of constructing rather messy ones. Our investigations are motivated by an intimate relationship between the pairs X, Y and minimal imperfect graphs.     

Disproof of a conjecture in graph reconstruction theory

In his thesis [3] B. D. Thatte conjectured that ifG=G ₁,G ₂,...G _n is a sequence of finitely many simple connected graphs (isomorphic graphs may occur in the sequence) with the same number of vertices and edges then their shuffled edge deck uniquely determines the graph sequence (up to a permutation). In this paper we prove that there are such sequences of graphs with the same shuffled edge deck.This research was partially supported by Hungarian National Foundation of Scientific Research Grant no. 1812