Strongly Even‐Cycle Decomposable Graphs

A graph is strongly even‐cycle decomposable if the edge set of every subdivision with an even number of edges can be partitioned into cycles of even length. We prove that several fundamental composition operations that preserve the property of being Eulerian also yield strongly even‐cycle decomposable graphs. As an easy application of our theorems, we give an exact characterization of the set of strongly even‐cycle decomposable cographs.     

Between clique-width and linear clique-width of bipartite graphs

We consider hereditary classes of bipartite graphs where clique-width is bounded, but linear clique-width is not. Our goal is identifying classes that are critical with respect to linear clique-width. We discover four such classes and conjecture that this list is complete, i.e. a hereditary class of bipartite graphs of bounded clique-width that excludes a graph from each of the four critical classes has bounded linear clique-width.     

Partial Characterizations of 1‐Perfectly Orientable Graphs

We study the class of 1‐perfectly orientable graphs, that is, graphs having an orientation in which every out‐neighborhood induces a tournament. 1‐perfectly orientable graphs form a common generalization of chordal graphs and circular arc graphs. Even though they can be recognized in polynomial time, little is known about their structure. In this article, we develop several results on 1‐perfectly orientable graphs. In particular, we (i) give a characterization of 1‐perfectly orientable graphs in terms of edge clique covers, (ii) identify several graph transformations preserving the class of 1‐perfectly orientable graphs, (iii) exhibit an infinite family of minimal forbidden induced minors for the class of 1‐perfectly orientable graphs, and (iv) characterize the class of 1‐perfectly orientable graphs within the classes of cographs and of cobipartite graphs. The class of 1‐perfectly orientable cobipartite graphs coincides with the class of cobipartite circular arc graphs.     

A good characterization of cograph contractions

A graph is called a graph contraction if it is obtained from a cograph (a graph with no induced path on four vertices) by contracting some pairwise disjoint independent sets and then making the “contracted” vertices pairwise adjacent. Cograph contractions are perfect and generalize cographs and split graphs. This article gives a good characterization of cograph contractions, solving a problem posed by M. Hujter and Zs. Tuza. © John Wiley & Sons, Inc. J Graph Theory 30: 309–318, 1999     

A note on the bichromatic numbers of graphs

For a pair of integers k, l≥0, a graph G is (k, l)‐colorable if its vertices can be partitioned into at most k independent sets and at most l cliques. The bichromatic number χ^b(G) of G is the least integer r such that for all k, l with k+l=r, G is (k, l)‐colorable. The concept of bichromatic numbers simultaneously generalizes the chromatic number χ(G) and the clique covering number θ(G), and is important in studying the speed of hereditary properties and edit distances of graphs. It is easy to see that for every graph G the bichromatic number χ^b(G) is bounded above by χ(G)+θ(G)?1. In this article, we characterize all graphs G for which the upper bound is attained, i.e., χ^b(G)=χ(G)+θ(G)?1. It turns out that all these graphs are cographs and in fact they are the critical graphs with respect to the (k, l)‐colorability of cographs. More specifically, we show that a cograph H is not (k, l)‐colorable if and only if H contains an induced subgraph G with χ(G)=k+1, θ(G)=l+1 and χ^b(G)=k+l+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 263–269, 2010     

Forbidden induced subgraph characterization of cograph contractions

Let S₁, S₂,…,S_t be pairwise disjoint non‐empty stable sets in a graph H. The graph H^* is obtained from H by: (i) replacing each S_i by a new vertex q_i; (ii) joining each q_i and q_j, 1 ≤ i # j ≤ t, and; (iii) joining q_i to all vertices in H – (S₁ ∪ S₂ ∪ ··· ∪ S_t) which were adjacent to some vertex of S_i. A cograph is a P₄‐free graph. A graph G is called a cograph contraction if there exist a cograph H and pairwise disjoint non‐empty stable sets in H for which G ? H^*. Solving a problem proposed by Le [ 2 ], we give a finite forbidden induced subgraph characterization of cograph contractions. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 217–226, 2004     

Free De Morgan Bisemigroups and Bisemilattices

We give a geometric representation of free De Morgan bisemigroups, free commutative De Morgan bisemigroups, and free De Morgan bisemilattices by using labeled graphs.2000 Mathematics Subject Classification: 08A70, 08B20This research was supported by the National Foundation of Scientific Research of Hungary under grant no. T30511.