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.     

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.     

The strong perfect graph conjecture holds for diamonded odd cycle-free graphs

In this paper, we show that the strong perfect graph conjecture holds for a new class of graphs which we call diamonded odd cycle-free graphs. The class of diamonded odd cycle-free graphs contains the classes of threshold graphs and K₄\e-free graphs.     

Partitionable graphs,circle graphs,and the berge strong perfect graph conjecture

Partitionable graphs have been studied by a number of authors in conjunction with attempts at proving the Berge Strong Perfect Graph Conjecture (SPGC). We give some new properties of partitionable graphs which can be used to give a new proof that the SPGC holds for K_1,3-free graphs. Finally, we will show that the SPGC also holds for the class of circle graphs.     

On the critical graph conjecture

Gol'dberg has recently constructed an infinite family of 3-critical graphs of even order. We now prove that if there exists a p(≥4)-critical graph K of odd order such that K has a vertex u of valency 2 and another vertex v ≠ u of valency ≤(p + 2)/2, then there exists a p-critical graph of even order.     

Families of graphs complete for the strong perfect graph Conjecture

The Strong Perfect Graph Conjecture states that a graph is perfect iff neither it nor its complement contains an odd chordless cycle of size greater than or equal to 5. In this article it is shown that many families of graphs are complete for this conjecture in the sense that the conjecture is true iff it is true on these restricted families. These appear to be the first results of this type.     

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 strong graph bundles

We study strong graph bundles : a concept imported from topology which generalizes both covering graphs and product graphs. Roughly speaking, a strong graph bundle always involves three graphs $E$, $B$ and $F$ and a projection $p:E\to B$ with fiber $F$ (i.e. $p^{?1}\left(x\right)?F$ for all $x\in V\left(B\right)$) such that the preimage of any edge $xy$ of $B$ is trivial (i.e. $p^{?1}\left(xy\right)?K_2?F$). Here we develop a framework to study which subgraphs $S$ of $B$ have trivial preimages (i.e. $p^{?1}\left(S\right)?S?F$) and this allows us to compare and classify several variations of the concept of strong graph bundle. As an application, we show that the clique operator preserves triangular graph bundles (strong graph bundles where preimages of triangles are trivial) thus yielding a new technique for the study of clique divergence of graphs.     

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 the spectrum of the perfect matching derangement graph

Journal of Algebraic Combinatorics - We prove the alternating sign conjecture for the perfect matching derangement graph.     

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.     

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.     

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.     

On the strong circular 5‐flow conjecture

The Strong Circular 5‐flow Conjecture of Mohar claims that each snark—with the sole exception of the Petersen graph—has circular flow number smaller than 5. We disprove this conjecture by constructing an infinite family of cyclically 4‐edge connected snarks whose circular flow number equals 5. © 2006 Wiley Periodicals, Inc. J Graph Theory