Search

In this paper, we introduce the notions of m-shadow graphs and n-splitting graphs,m ≥ 2, n ≥ 1. We prove that, the m-shadow graphs for paths, complete bipartite graphs and symmetric product between paths and null graphs are odd graceful. In addition, we show that, the m-splitting graphs for paths, stars and symmetric product between paths and null graphs are odd graceful. Finally, we present some examples to illustrate the proposed theories.

The vertices of a graph are classified into seven types by J.T. Hedetniemi, S.M. Hedetniemi, S.T. Hedetniemi and T.M. Lewis and they ask the following questions: (1) What is the smallest order n of a graph having $$n-2$$ very typical vertices or $$n-2$$ typical vertices? (2) What is the smallest order of a pantypical graph? We answer these two questions and determine all the possible orders of the graphs in these three classes in this paper.

In this article, a technique to construct cyclic orthogonal double covers (CODCs) of regular circulant graphs by certain infinite graph classes such as complete bipartite and tripartite graphs and disjoint union of butterfly and K 1 , 2 n − 10 is introduced.

In this paper, we derive bounds on the optimal average information ratio of the access structures based on general graphs and investigate the value of the ratio for unicycle graphs and some bipartite graphs. We determine the exact values of this ratio for some infinite classes of bipartite graphs and unicycle graphs. This extends previous results. We also provide good bounds on the optimal average information ratio for all unicycle graphs.

In this paper we characterize distance-regular graphs with diameter three having exactly three distinct distance eigenvalues, and also bipartite distance-regular graphs with diameter four having three distinct distance eigenvalues. We derive some properties and give particular examples of such graphs. We also present an infinite family of bipartite semiregular graphs with diameter four having exactly four distinct distance eigenvalues. With these results, we address some problems posed in Atik and Panigrahi (2015) [3] .

In this article, we characterize various algebraic and order structures whose zero-divisor graphs are perfect graphs. We strengthen the result of Chenź(2003, Theorem 2.5) by providing a simpler proof of Beck's conjecture for the class of finite reduced rings (not necessarily commutative).

Strongly perfect graphs have been studied by several authors (e.g. Berge and Duchet (1984) [1], Ravindra (1984) [12] and Wang (2006) [14]). In a series of two papers, the current paper being the first one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [14] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.

In 1962, Erd\H{o}s proved a theorem on the existence of Hamilton cycles in graphs with given minimum degree and number of edges. Significantly strengthening in case of balanced bipartite graphs, Moon and Moser proved a corresponding theorem in 1963. In this paper we establish several spectral analogues of Moon and Moser's theorem on Hamilton paths in balanced bipartite graphs and nearly balanced bipartite graphs. One main ingredient of our proofs is a structural result of its own interest, involving Hamilton paths in balanced bipartite graphs with given minimum degree and number of edges., Comment: 14 pages, 2 figures, Version 2 differs from Version 1 in improved presentation, to appear in Linear Algebra and Its Applications

We obtain a sharp result that for any even n ? 34, every {Dn,Dn+1}-regular graph of order n contains ?n/4? disjoint perfect matchings, where Dn = 2?n/4?-1. As a consequence, for any integer D ? Dn, every {D, D+1}- regular graph of order n contains (D-?n/4?+1) disjoint perfect matchings.

Let P t and C l denote a path on t vertices and a cycle on l vertices, respectively. In this paper we study the k-COLORING problem for (P t ,C l)-free graphs. It has been shown by Golovach, Paulusma, and Song that when l = 4 all these problems can be solved in polynomial time. By contrast, we show that in most other cases the k-COLORING problem for (P t ,C l)-free graphs is NP-complete. Specifically, for l = 5 we show that k-COLORING is NP-complete for (P t ,C 5)-free graphs when k ≥ 4 and t ≥ 7; for l ≥ 6 we show that k-COLORING is NP-complete for (P t ,C l)-free graphs when k ≥ 5, t ≥ 6; and additionally, we prove that 4-COLORING is NP-complete for (P t ,C l)-free graphs when t ≥ 7 and l ≥ 6 with l ≠ 7, and that 4-COLORING is NP-complete for (P t ,C l)-free graphs when t ≥ 9 and l ≥ 6 with l ≠ 9. It is known that, generally speaking, for large k the k-COLORING problem tends to remain NP-complete when one forbids an induced path P t with large t. Our findings mean that forbidding an additional induced cycle C l (with l > 4) does not help. We also revisit the problem of k-COLORING (P t ,C 4)-free graphs, in the case t = 6. (For t = 5 the k-COLORING problem is known to be polynomial even on just P 5-free graphs, for every k.) The algorithms of Golovach, Paulusma, and Song are not practical as they depend on Ramsey-type results, and end up using tree-decompositions with very high widths. We develop more practical algorithms for 3-COLORING and 4-COLORING on (P 6,C 4)-free graphs. Our algorithms run in linear time if a clique cutset decomposition of the input graph is given. Moreover, our algorithms are certifying algorithms. We provide a finite list of all minimal non-k-colorable (P 6,C 4)-free graphs, for k = 3 and k = 4. Our algorithms output one of these minimal obstructions whenever a k-coloring is not found. In fact, we prove that there are only finitely many minimal non-k-colorable (P 6,C 4)-free graphs for any fixed k; however, we do not have the explicit lists for higher k, and thus no certifying algorithms. (We note there are infinitely many non-k-colorable P 5-free, and hence P 6-free, graphs for any given k ≥ 4, according to a result of Hoang, Moore, Recoskie, Sawada, and Vatshelle.)

A trivial lower bound on the chromatic number of a graph is its clique number. In general, there is no upper bound on the chromatic number as a function of its clique number. Indeed, a famous result of Erdős establishes the existence of graphs with arbitrary large chromatic number and no triangle. However, well-structured classes of graphs may admit such a function: we say that a hereditary class of graphs, i.e., a class closed under taking induced subgraphs, is _$\chi$-bounded_ if there exists a function $f$ such that the chromatic number of every graph in the class is at most $f(\omega)$, where $\omega$ is its clique number. The most prominent $\chi$-bounded class of graphs is the class of [perfect graphs](https://en.wikipedia.org/wiki/Perfect_graph), i.e., graphs $G$ such that the chromatic number of every induced subgraph of $G$ is equal to its clique number. Here, the function $f$ from the definition of $\chi$-bounded class is the identity. The [Strong Perfect Graph Theorem](https://en.wikipedia.org/wiki/Strong_perfect_graph_theorem) of Chudnovsky, Robertson, Seymour and Thomas asserts that a graph is perfect if and only if it does not contain an odd cycle or its complement as an induced subgraph. Hence, perfect graphs include, among many other graph classes, interval graphs and more generally chordal graphs. The authors consider graphs with bounded rank-width, or equivalently [clique-width](https://en.wikipedia.org/wiki/Clique-width). Informally speaking, such graphs can be iteratively decomposed along simple structured cuts to single vertices. Decompositions along such cuts are assumed to play a key role in the characterization of graph classes closed under taking vertex minors analogously to the role of [tree decompositions](https://en.wikipedia.org/wiki/Tree_decomposition) in the [Graph Structure Theorem](https://en.wikipedia.org/wiki/Graph_structure_theorem) for graph classes closed under taking minors. Dvořak and Kraľ proved a conjecture of Geelen that every class of graphs with bounded rank-width is $\chi$-bounded, however, their function $f$ is exponential. The authors significantly improve this by showing that the function $f$ can be chosen to be polynomial and actually prove a more general statement concerning graphs decomposable along simple structured cuts to graphs from a polynomially $\chi$-bounded class. In the case of rank-width, the degree of the polynomial depends on the rank-width and this dependence is shown to be necessary.

A connected undirected graph G is 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 ) . Ageev, Kostochka, and Szigeti characterized Seymour graphs in 1997. In this paper, we characterize minimal non-Seymour graphs. More precisely, we show that minimal non-Seymour graphs can be completely described by two infinite families of graphs, and we provide a procedure to construct them. Our characterization also generalizes a theorem of Lovasz concerning minimal nonbipartite matching-covered graphs.

In this paper we characterize all bipartite graphs with at most six non-zero eigenvalues. We determine the eigenvalues of bipartite graphs that have at most four nonzero eigenvalues. V tem članku karakteriziramo vse dvodelne grafe z največ šestimi neničelnimi lastnimi vrednostmi. Določimo lastne vrednosti dvodelnih grafov ki imajo največ štiri neničelne lastne vrednosti.

Several versions of the Riemann–Hurwitz theorem for branched coverings of graphs are presented. A larger class of graphs which may have not only multiple edges but also loops and darts is considered. This makes it possible to render the class of graphs closed with respect to morphisms arising as quotient maps for actions of finite groups.

The theory of matching energy of graphs since been proposed by Gutman and Wagner in 2012, has attracted more and more attention. It is denoted by B n , m , the class of bipartite graphs with order n and size m. In particular, B n , n denotes the set of bipartite unicyclic graphs, which is an interesting class of graphs. In this paper, for odd n, we characterize the bipartite unicyclic graphs with the first ? n - 3 4 ? largest matching energies. There is an interesting correspondence: we conclude that the graph with the second maximal matching energy in B n , n for odd n ? 11 is P n 6 , which is the only graph attaining the maximum value of the energy among all the (bipartite) unicyclic graphs for n ? 16.

Counting the number of perfect matchings in graphs is a computationally hard problem. However, in the case of planar graphs, and even for K3,3-free graphs, the number of perfect matchings can be computed efficiently. The technique to achieve this is to compute a Pfaffian orientation of a graph. In the case of K5-free graphs, this technique will not work because some K5-free graphs do not have a Pfaffian orientation. We circumvent this problem and show that the number of perfect matchings in K5-free graphs can be computed in polynomial time. We also parallelize the sequential algorithm and show that the problem is in TC2. We remark that our results generalize to graphs without singly-crossing minor.

A graph $G$ is \emph{trivially perfect} if for every induced subgraph the cardinality of the largest set of pairwise nonadjacent vertices (the stability number) $\alpha(G)$ equals the number of (maximal) cliques $m(G)$. We characterize the trivially perfect graphs in terms of vertex-coloring and we extend some definitions to infinite graphs.

Since the critical graphs of order n ≤ 14 were studied so far [1] , [2] , [3] , [4] , [6] , [11] , in this paper, we are concerned with 5-critical graphs of order 15. This paper gives the complete possible list of degree sequences of 5-critical graphs of order 15.

We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-join and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behaviour of the extension complexity under these graph operations. We show bounds for the extension complexity of the stable set polytope of a perfect graph $G$ depending linearly on the size of $G$ and involving the depth of a decomposition tree of $G$ in terms of basic perfect graphs., 17 pages

The mirror (or bipartite complement) $${{\mathrm{mir}}}(B)$$mir(B) of a bipartite graph $$B=(X,Y,E)$$B=(X,Y,E) has the same color classes $$X$$X and $$Y$$Y as $$B$$B, and two vertices $$x \in X$$x?X and $$y \in Y$$y?Y are adjacent in $${{\mathrm{mir}}}(B)$$mir(B) if and only if $$xy \notin E$$xy?E. A bipartite graph is chordal bipartite if none of its induced subgraphs is a chordless cycle with at least six vertices. In this paper, we deal with chordal bipartite graphs whose mirror is chordal bipartite as well; we call these graphs auto-chordal bipartite graphs (ACB graphs for short). We characterize ACB graphs, show that ACB graphs have unbounded bipartite Dilworth number, and we characterize ACB graphs with bipartite Dilworth number $$k$$k.

We characterize the graphs for which a linear relaxation of a facility location problem defines a polytope with all integral extreme points. We use a transformation to a stable set problem in perfect graphs. Based on this transformation, these graphs can be recognized in polynomial time.

We study the perfect colorings of infinite circulant graphs whose set of distances constitutes the segment of naturals [1, n]. We give a complete description of the perfect colorings of these graphs with two colors and list all their admissible parameters.

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O (| V |(| E | + | V | log| V |))-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which is also introduced in the present article. Despite being weaker than the structural results for claw-free graphs given by Chudnovsky and Seymour [2005, 2008a, 2008b] our decomposition theorem is, on the other hand, algorithmic, that is, it is coupled with an O (| V || E |)-time algorithm that actually produces the decomposition.

SUMMARY Ordered Binary Decision Diagrams (OBDDs for short) are popular dynamic data structures for Boolean functions. In some modern applications, we have to handle such huge graphs that the usual explicit representations by adjacency lists or adjacency matrices are infeasible. To deal with such huge graphs, OBDD-based graph representations and algorithms have been investigated. Although the size of OBDD representations may be large in general, it is known to be small for some special classes of graphs. In this paper, we show upper bounds and lower bounds of the size of OBDDs representing some intersection graphs such as bipartite permutation graphs, biconvex graphs, convex graphs, (2-directional) orthogonal ray graphs, and permutation graphs.

Fuzzy antihat graphs are graphs obtained as 2-clique-bond compositions of fuzzy line graphs with three different types of three-cliqued graphs. By the decomposition theorem of Chudnovsky and Seymour [2] , fuzzy antihat graphs form a large subclass of claw-free, not quasi-line graphs with stability number at least four and with no 1-joins. A graph is W -perfect if its stable set polytope is described by: nonnegativity, rank, and lifted 5-wheel inequalities. By exploiting the polyhedral properties of the 2-clique-bond composition, we prove that fuzzy antihat graphs are W -perfect and we move a crucial step towards the solution of the longstanding open question of finding an explicit linear description of the stable set polytope of claw-free graphs.

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].

A graph is an opposition graph, respectively, a coalition graph, if it admits an acyclic orientation which puts the two end-edges of every chordless 4-vertex path in opposition, respectively, in the same direction. Opposition and coalition graphs have been introduced and investigated in connection to perfect graphs. Recognizing and characterizing opposition and coalition graphs still remain long-standing open problems. The present paper gives characterizations for co-bipartite opposition graphs and co-bipartite coalition graphs, and for bipartite opposition graphs. Implicit in our argument is a linear time recognition algorithm for these graphs. As an interesting by-product, we find new submatrix characterizations for the well-studied bipartite permutation graphs.

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 this paper we deal with several subclasses of self complementary chordal graphs characterized by single forbidden induced subgraph namely Chairfree sc chordal graphs, H-free sc chordal graphs and Cross (star1, 1, 1, 2)-free sc chordal graphs. We obtain some results on these classes and an algorithm is proposed based on these results that recognize these classes. We also compile a catalogue of (chair or H or or cross)-free sc chordal graphs upto 17 vertices.

The interaction property or the Fine--Wilf property for periodic partial words is studied. Partial words with two periods are represented by bipartite graphs and the interaction property is related to the edge connectedness property of these graphs. Threshold functions for the edge connectedness of random bipartite graphs and multigraphs are found. As a corollary, the interaction property is described in probabilistic terms.

A graph is well-covered if all its maximal independent sets have the same order. For a well-covered graph G of order n ( G ) without an isolated vertex, Claude Berge (C. Berge, Some common properties for regularizable graphs, edge-critical graphs and b -graphs, Ann. Discrete Math. 12 (1982) 31–44) proved that the independence number α ( G ) of G is at most n ( G ) 2 . The extremal graphs for this result are known as the very well-covered graphs and were characterized by Odile Favaron (O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177–187). We extend these two results in two different ways. First, we study the structure and recognition of the well-covered graphs G without an isolated vertex that have independence number n ( G ) − k 2 for some non-negative integer k . For k = 1 , we give a complete structural description of these graphs, and for a general but fixed k , we describe a polynomial time recognition algorithm. Second, we relax the condition of well-coveredness and consider graphs G without an isolated vertex for which the independence number α ( G ) and the independent domination number i ( G ) satisfy α ( G ) − i ( G ) ≤ k for some non-negative integer k . We prove a suitable version of Berge’s result for these graphs, derive an upper bound on the independence number as a corollary, and discuss its relation to Favaron’s characterization.

Petersen proved that every 3-regular brigdeless graph has a perfect matching. Motivated by this result, several authors established lower bounds on the matching number of a graph subject to degree and girth conditions. In 2012 Henning et al. proved such a lower bound for connected 3-regular graphs. In the present paper, we extend their result by establishing lower bounds on the matching number of graphs of given odd regularity d and odd girth g , which are sharp for many values of d and g . For d = g = 5 , we characterize all extremal graphs.

The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the König-Egerváry property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the König-Egerváry property by means of forbidden subgraphs within graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovász´s result to a characterization of all graphs having the König-Egerváry property in terms of forbidden configurations (which are certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the König-Egerváry property by means of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. Using our characterization of graphs with the König-Egerváry property, we also prove a forbidden subgraph characterization for the class of edge-perfect graphs. Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Dourado, Mitre C.. Universidade Federal do Rio de Janeiro; Brasil Fil: Duran, Guillermo Alfredo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Universidad de Chile; Chile. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Faria, Luerbio. Universidade do Estado do Rio de Janeiro; Brasil Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Safe, Martin Dario. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina

This article gives a survey of all results on the power graphs of groups and semigroups obtained in the literature. Various conjectures due to other authors, questions and open problems are also included.

We study the Lovasz-Schrijver SDP-operator applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the SDP-operator generates the stable set polytope in one step has been open since 1990. In an earlier publication, we named these graphs N + -perfect. In the current contribution, we propose a conjecture on combinatorial characterization of N + -perfect graphs and make progress towards such a full combinatorial characterization by establishing a new, close relationship among N + -perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs.

A lemma of Fouquet implies that a claw-free graph contains an induced C"5, contains no odd hole, or is quasi-line. In this paper, we use this result to give an improved shortest-odd-hole algorithm for claw-free graphs by exploiting the structural relationship between line graphs and quasi-line graphs suggested by Chudnovsky and Seymour's structure theorem for quasi-line graphs. Our approach involves reducing the problem to that of finding a shortest odd cycle of length >=5 in a graph. Our algorithm runs in O(m^2+n^2logn) time, improving upon Shrem, Stern, and Golumbic's recent O(nm^2) algorithm, which uses a local approach. The best known recognition algorithms for claw-free graphs run in O(m^1^.^6^9)@?O(n^3^.^5) time, or O(m^2)@?O(n^3^.^5) without fast matrix multiplication.

A graph is perfect if the chromatic number is equal to the clique number for every induced subgraph of the graph. Perfect graphs were defined by Berge in the sixties. In this survey we present known results about partial characterizations by forbidden induced subgraphs of different graph classes related to perfect graphs. We analyze a variation of perfect graphs, clique-perfect graphs, and two subclasses of perfect graphs, coordinated graphs and balanced graphs.

Connectivity and edge-connectivity of a graph measure the difficulty of breaking the graph apart, but they are very much affected by local aspects like vertex degree. Average connectivity (and analogously, average edge-connectivity ) has been introduced to give a more refined measure of the global “amount” of connectivity. In this paper, we prove a relationship between the average connectivity and the matching number in all graphs. We also give the best lower bound for the average edge-connectivity over n -vertex connected cubic graphs, and we characterize the graphs where equality holds. In addition, we show that this family has the fewest perfect matchings among cubic graphs that have perfect matchings.

A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes. Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Duran, Guillermo Alfredo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Universidad de Chile; Chile. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Safe, Martin Dario. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Wagler, Annegret K.. Universite Blaise Pascal; Francia

The spectral excess theorem for distance-regular graphs states that a regular (connected) graph is distance-regular if and only if its spectral excess equals its average excess. Recently, some local as well as global approaches to this result have been used to obtain new versions of the theorem for nonregular graphs, and also to study the problem of characterizing those graphs which have the corresponding distance-regularity property. In this paper such approaches are compared and related. In particular, a recent inequality of Lee and Weng for nonregular graphs, which is similar to the one that leads to the spectral excess theorem, is improved. As a consequence, we obtain new characterizations of some properties related to that of distance-regularity. For instance, a sufficient condition for to be distance-polynomial is obtained.

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.

The maximum induced matching problem is known to be APX-hard in the class of bipartite graphs. Moreover, the problem is also intractable in this class from a parameterized point of view, i.e. it is W[1]-hard. In this paper, we reveal several classes of bipartite (and more general) graphs for which the problem admits fixed-parameter tractable algorithms. We also study the computational complexity of the problem for regular bipartite graphs and prove that the problem remains APX-hard even under this restriction. On the other hand, we show that for hypercubes (a proper subclass of regular bipartite graphs) the problem admits a simple solution.

The perfect-matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings in G. This paper characterizes bipartite and nearly bipartite graphs whose 1-skeleton graphs of perfect-matching polytopes have diameter 1. � 2012 Elsevier B.V. All rights reserved.

In a connected graph G, the status of a vertex is the sum of the distances of that vertex to each of the other vertices in G. The subgraph induced by the vertices of minimum (maximum) status in G is called the median (anti-median) of G. A bipartite graph G is symmetric if for a bi-partition (X, Y) of G, there is a map f from X onto Y such that if \((u,f(v)) \in E(G)\), then \((v,f(u)) \in E(G)\), where \(u,v\in X\). In this paper we show, by construction, that any symmetric bipartite graph is a median (anti-median, center) of another symmetric bipartite graph. We also obtain results on median and anti-median problem on square graphs of bi-partite graphs with equal partitions.

In this paper we consider the class of simple graphs defined by excluding, as induced subgraphs, even holes (i.e. chordless cycles of even length). These graphs are known as even-hole-free graphs. We prove a decomposition theorem for even-hole-free graphs, that uses star cutsets and 2-joins. This is a significant strengthening of the only other previously known decomposition of even-hole-free graphs, by Conforti, Cornuéjols, Kapoor and Vušković, that uses 2-joins and star, double star and triple star cutsets. It is also analogous to the decomposition of Berge (i.e. perfect) graphs with skew cutsets, 2-joins and their complements, by Chudnovsky, Robertson, Seymour and Thomas. The similarity between even-hole-free graphs and Berge graphs is higher than the similarity between even-hole-free graphs and simply odd-hole-free graphs, since excluding a 4-hole, automatically excludes all antiholes of length at least 6. In a graph that does not contain a 4-hole, a skew cutset reduces to a star cutset, and a 2-join in the complement implies a star cutset, so in a way it was expected that even-hole-free graphs can be decomposed with just the star cutsets and 2-joins. A consequence of this decomposition theorem is a recognition algorithm for even-hole-free graphs that is significantly faster than the previously known ones.

A Graph G is Super Strongly Perfect Graph if every induced sub graph H of G possesses a minimal dominating set that meets all the maximal complete sub graphs of H. Bipartite graphs, Complete graphs etc., are some of the most important classes of Super Strongly Perfect graphs. Here, we summarize the results concerning Super Strongly Perfect graphs. We investigate some classes of Super Strongly Perfect graphs and we investigate the structure of Super Strongly Perfect Graphs.

A cycle transversal (or feedback vertex set) of a graph G is a subset T@?V(G) such that T@?V(C) 0@? for every cycle C of G. This work considers the problem of finding special cycle transversals in perfect graphs and cographs. We prove that finding a minimum cycle transversal T in a perfect graph G is NP-hard, even for bipartite graphs with maximum degree four. Since G-T is acyclic, this result implies that finding a maximum acyclic induced subgraph of a perfect graph is also NP-hard. Other special properties of T are considered. A clique (stable, respectively) cycle transversal, or simply cct (sct, respectively) is a cycle transversal which is a clique (stable set, respectively). Recognizing graphs which admit a cct can be done in polynomial time; however, no structural characterization of such graphs is known, even for perfect graphs. We characterize cographs with cct in terms of forbidden induced subgraphs and describe their structure. This leads to linear time recognition of cographs with cct. We also prove that deciding whether a perfect graph admits an sct is NP-complete. We characterize cographs with sct in terms of forbidden induced subgraphs; this characterization also leads to linear time recognition.

We consider the minimum feedback vertex set problem for some bipartite graphs and degree-constrained graphs. We show that the problem is linear time solvable for bipartite permutation graphs and NP-hard for grid intersection graphs. We also show that the problem is solvable in O(n(2) log(6) n) time for n-vertex graphs with maximum degree at most three.