Search

A 1-factorization of a graph G is a decomposition of G into edge-disjoint 1-factors (perfect matchings), and a perfect 1-factorization is a 1-factorization in which the union of any two of the 1-factors is a Hamilton cycle. We consider the problem of the existence of perfect 1-factorizations of even order 4-regular Cayley graphs, with a particular interest in circulant graphs. In this paper, we study a new family of graphs, denoted D h,k , which are Cayley graphs if and only if k is even or h = 2. By solving the perfect 1-factorization problem for a large class of D h,k graphs, we obtain a new class of 4-regular bipartite circulant graphs that do not have a perfect 1-factorization, answering a problem posed in [7]. With further study of D h,k graphs, we prove the nonexistence of P1Fs in a class of 4-regular non-bipartite circulant graphs, which is further support for a conjecture made in [7].

The clique numberωD of a digraph D is the size of the largest bidirectionally complete subdigraph ofi¾?D. D is perfect if, for any induced subdigraph H of D, the dichromatic number i¾?H defined by Neumann-Larai¾?The dichromatic number of a digraph, J. Combin. Theory Ser. B 33 1982, 265-270 equals the clique number ωH. Using the Strong Perfect Graph Theoremi¾?M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann. Math. 164 2006, 51-229 we give a characterization of perfect digraphs by a set of forbidden induced subdigraphs. Modifying a recent proof of Bang-Jensen eti¾?al.i¾?Finding an induced subdivision of a digraph, Theoret. Comput. Sci. 443 2012, 10-24 we show that the recognition of perfect digraphs is co-NP-complete. It turns out that perfect digraphs are exactly the complements of clique-acyclic superorientations of perfect graphs. Thus, we obtain as a corollary that complements of perfect digraphs have a kernel, using a result of Boros and Gurvichi¾?Perfect graphs are kernel solvable, Discrete Math. 159 1996, 35-55. Finally, we prove that it is NP-complete to decide whether a perfect digraph has a kernel.

The second author's B.A.R. ω, Δ, i¾? conjecture proposes that every graph satisfies i¾?i¾?i¾?12Δ+1+ωi¾?. In this article, we prove that the conjecture holds for all claw-free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way, we discuss a stronger local conjecture, and prove that it holds for claw-free graphs with a three-colorable complement. To prove our results, we introduce a very useful i¾?-preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so-called skeletal graphs.

In 1988, Chvatal and Sbihi (J Combin Theory Ser B 44(2) (1988), 154–176) proved a decomposition theorem for claw-free perfect graphs. They showed that claw-free perfect graphs either have a clique-cutset or come from two basic classes of graphs called elementary and peculiar graphs. In 1999, Maffray and Reed (J Combin Theory Ser B 75(1) (1999), 134–156) successfully described how elementary graphs can be built using line-graphs of bipartite graphs using local augmentation. However, gluing two claw-free perfect graphs on a clique does not necessarily produce claw-free graphs. In this article, we give a complete structural description of claw-free perfect graphs. We also give a construction for all perfect circular interval graphs.

We study the perfect 2-colorings (also known as the equitable partitions into two parts or the completely regular codes with covering radius 1) of the Johnson graphs . In particular, we classify all the realizable quotient matrices of perfect 2-colorings for odd v. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 21: 232–252, 2013

Let G be a bridgeless cubic graph. Fulkerson conjectured that there exist six 1-factors of G such that each edge of G is contained in exactly two of them. Berge conjectured that the edge-set of G can be covered with at most five 1-factors. We prove that the two conjectures are equivalent. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:125-128, 2011 © 2011 Wiley Periodicals, Inc.

The structure of previous known infinite families of crossing-critical graphs had led to the conjecture that crossing-critical graphs have bounded bandwidth. If true, this would imply that crossing-critical graphs have bounded degree, that is, that they cannot contain subdivisions of K1, n for arbitrarily large n. In this article we prove two new results that revolve around this question. On the positive side, we show that crossing-critical graphs cannot contain subdivisions of K2, n for arbitrarily large n. On the negative side, we show that there are simple 3-connected graphs with arbitrarily large maximum degree that are 2-crossing-critical in the projective plane. Although the former conjecture is now disproved in a subsequent manuscript by Dvořak and Mohar, our results are not affected, and some interesting questions remain. Namely, can the bandwidth conjecture still be true for simple 3-connected graphs in the plane? © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 198–215, 2010 © 2010 Wiley Periodicals, Inc.

A connected undirected graph G is called a Seymour graph if the maximum number of edge disjoint T-cuts is equal to the cardinality of a minimum T-join for every even subset T of V(G). Several families of graphs have been shown to be subfamilies of Seymour graphs (Seymour[5][6], Gerards [1], Szigeti [7]). In this paper we prove a characterization of Seymour graphs which was conjectured by Sebo and implies the results mentioned above.

Neighborhood-perfect graphs form a subclass of the perfect graphs if the Strong Perfect Graph Conjecture of C. Berge is true. However, they are still not shown to be perfect. Here we propose the characterization of neighborhood-perfect graphs by studying minimal non-neighborhood-perfect graphs (MNNPG). After presenting some properties of MNNPGs, we show that the only MNNPGs with neighborhood independence number one are the 3-sun and K. Also two further classes of neighborhood-perfect graphs are presented: line-graphs of bipartite graphs and a zfree cographs. 0 1996 John Wiley & Sons, Inc.

We present a new algorithm for coloring perfect graphs and use it to color the parity orderable graphs, a class which strictly contains parity graphs. Also, we modify this algorithm to obtain an O(m2 + n) locally perfect coloring algorithm for parity graphs. © 1995 John Wiley & Sons, Inc.

The notion of p-proportional graphs comes from the study of subgraph counts in random graphs, where the p-proportional graphs occur as exceptional cases in a central limit theorem. In this paper we show that p-proportional graphs exist for all rational p, 0 < p < 1, and thereby proving a conjecture from [3]. © 1993 John Wiley & Sons, Inc.

A graph G is domination perfect if for each induced subgraph H of G, γ(H) = i(H), where γ and i are a graph's domination number and independent domination number, respectively. Zverovich and Zverovich [3] offered a finite forbidden induced characterization of domination perfect graphs. This characterization is not correct, but the ideas in [3] can be used to weaken the known sufficient conditions for a graph to be domination perfect and to obtain short proofs of some results regarding domination perfect graphs. © 1993 John Wiley & Sons, Inc.

The study of perfectness, via the strong perfect graph conjecture, has given rise to numerous investigations concerning the structure of many particular classes of perfect graphs. In “Perfect Product Graphs” (Discrete Mathematics, Vol. 20, 1977, pp. 177--186), G. Ravindra and K. R. Parthasarathy tried, but unfortunately without success, to characterize the perfectness of the cartesian product of graphs (see also MR No. 58--10567, 1979). In this paper we completely characterize the graphs that are both nontrivial cartesian products and s-strongly perfect.

The Hungarian method is an efficient algorithm for finding a minimal-cost perfect matching in a weighted bipartite graph. This paper describes an efficient algorithm for finding all minimal-cost perfect matchings. The computational time required to generate each additional perfect matching is O(n(n + m)), and it requires O(n + m) memory storage. This problem can be solved by algorithms for finding the Kth-best solution of assignment problems. However, the memory storage required by the known algorithms grows in proportion to K, and, hence, it may grow exponentially in n. So, our specialized algorithm has a considerable advantage in memory requirement over the precious more general algorithms for Kth-best assignment problems. Here we will show that the enumeration of all minimal-cost perfect matchings can be reduced to the enumeration of all perfect matchings in some bipartite graph. Therefore, our algorithm can be seen as an algorithm for enumerating all perfect matchings in a given bipartite graph.

Let γ(G) and i(G) be the domination number and independent domination number of a graph G, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) = i(H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization of domination perfect graphs. Bollobas and Cockayne [4] proved an inequality relating γ(G) and i(G) for the class of K1,k ‐free graphs. It is shown that the same inequality holds for a wider class of graphs. Copyright © 1991 Wiley Periodicals, Inc., A Wiley Company

A new characterization of maximum matchings for bipartite graphs is presented. It is based on “strong spanning trees” and permits the development of a new algorithm that does not use the classical notion of augmenting paths and that runs in O(|V| |E|) time for bipartite graphs with |V| nodes and |E| edges.

Ki-perfect graphs are a special instance of F - G perfect graphs, where F and G are fixed graphs with F a partial subgraph of G. Given S, a collection of G-subgraphs of graph K, an F - G cover of S is a set of T of F-subgraphs of K such that each subgraph in S contains as a subgraph a member of T. An F - G packing of S is a subcollection S′⊆ S such that no two subgraphs in S′ have an F-subgraph in common. K is F - G perfect if for all such S, the minimum cardinality of an F - G cover of S equals the maximum cardinality of an F - G packing of S. Thus Ki-perfect graphs are precisely Ki-1 - Ki perfect graphs. We develop a hypergraph characterization of F - G perfect graphs that leads to an alternate proof of previous results on Ki-perfect graphs as well as to a characterization of F - G perfect graphs for other instances of F and G.

A graph G is perfect in the sense of Berge if for every induced subgraph G′ of G, the chromatic number χ(G′) equals the largest number ω(G′) of pairwise adjacent vertices in G′. The Strong Perfect Graph Conjecture asserts that a graph G is perfect if, and only if, neither G nor its complement Ḡ contains an odd chordless cycle of length at least five. We prove that the conjecture is true for a class of P5-free graphs.

The class of superperfect graphs, which was previously studied by A. J. Hoffman, E. L. Johnson, and M. C. Golumbic, is a proper subclass of the class of perfect graphs; further, it properly contains the class of comparability graphs. In his book, Golumbic proves that, for split graphs, G is a comparability graph if and only if G is superperfect. Moreover, the fact that split graphs are exactly those graphs which are both triangulated and cotriangulated motivated Golumbic to ask if it is true or false that, for triangulated (or cotriangulated) graphs, G is a comparability graph if and only if G is superperfect. In the present paper, we determine those members of Gallai's list of minimal noncomparability graphs which are superperfect and, as a consequence, we find that the answer to the above question is “false” for triangulated and “true” for cotriangulated graphs.

In this paper some extremal properties of 3-colorings of bipartite complete graphs in the class of all bipartite p-threshold graphs that are uniquely 2-colorable are proved. As a consequence it is shown that the complete bipartite graphs Kp, p + r where p ⩾ 2 and 0 ⩽ r < are chromatically unique. A useful result concerning the maximization of a sum of powers of two under certain restrictions, which has an arithmetical interest, is also presented.

Summary Golumbic and Goss [5] introduced the class of chordal bipartite graphs, which was shown to be the bipartite analog of triangulated graphs. This paper completes the connection by proving a stronger theorem for chordal bipartite graphs and by deriving some previously known results on triangulated graphs.

We consider in this paper graphs which remain hamiltonian after the removal of k edges (k-edge hamiltonian) or k vertices (k-hamiltonian). These classes of graphs arise from reliability considerations in network design. In a previous paper, W. W. Wong and C. K. Wong presented families of minimum k-hamiltonian graphs and minimum k-edge hamiltonian graphs for k even. Here, we complete this study in the case where k is odd.

Current graphs and a theorem of White are used to show the existence of almost complete regular bipartite graphs with quadrilateral embeddings conjectured by Pisanski. Decompositions of Kn and Kn, n into graphs with quadrilateral embeddings are discussed, and some thickness results are obtained. Some new genus results are also obtained.

We define two types of bipartite graphs, chordal bipartite graphs and perfect elimination bipartite graphs, and prove theorems analogous to those of Dirac and Rose for chordal graphs (rigid circuit graphs, triangulated graphs). Our results are applicable to Gaussian elimination on sparse matrices where a sequence of pivots preserving zeros is sought. Our work removes the constraint imposed by Haskins and Rose that pivots must be along the main diagonal.

We derive three equivalent conditions on a perfect graph concerning the optimal solution of a convex programming problem, the length-width inequality, and the simultaneous vertex covering by cliques and anticliques. By combining proof techniques including Lagrangian dual, Dilworth's Theorem, and Kuhn-Tucker Theorem, we establish a strong connection between the three topics. This provides new insights into the structure of perfect graphs. The famous Lubell-Yamamoto-Meschalkin (LYM) Property or Sperner Property for partially ordered sets is a specialization of our results to a subclass of perfect graphs.

We prove that any graph with maximum degree n which can be obtained by removing exactly 2n - 1 edges from the join K1 + Kn, n is n-critical. This generalizes special constructions of critical graphs by S. Fiorini and H. P. Yap, and suggests a possible extension of another general construction due to Yap.

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.

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.

Whitney's theorem on line graphs is extended to the class of generalized line graphs defined by Hoffman.

In this note a shortened proof is given for the Faudree—Schelp theorem on path-connected graphs.