Bull-Free Weakly Chordal Perfectly Orderable Graphs

 Using doubly lexical orders and the notion of box partition due to de Figueiredo, Maffray, and Porto, we show that a certain subclass of bull-free weakly chordal graphs is perfectly orderable. This together with results of de Figueiredo, Maffray, and Porto confirms Chvátal's conjecture that bull-free graphs with no anti-hole and no odd hole are perfectly orderable; here hole means induced cycle with five or more vertices. Received: September 21, 1998?Final version received: January 23, 2001     

Some classes of perfectly orderable graphs

In 1981, Chvátal defined the class of perfectly orderable graphs. This class of perfect graphs contains the comparability graphs and the triangulated graphs. In this paper, we introduce four classes of perfectly orderable graphs, including natural generalizations of the comparability and triangulated graphs. We provide recognition algorithms for these four classes. We also discuss how to solve the clique, clique cover, coloring, and stable set problems for these classes.     

A New Class of Brittle Graphs

A graph G is perfectly orderable in the sense of Chvátal if there exists a linear order on the set of vertices of G such that no induced path with vertices a, b, c, d and edges ab, bc, cd has a < b and d < c. A perfectly orderable graph G is brittle if every induced subgraph of G contains a vertex which is either endpoint or midpoint of no induced path with three edges in G. We present a new class of brittle graphs by forbidden configurations.     

A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture

A well‐known combinatorial theorem says that a set of n non‐collinear points in the plane determines at least n distinct lines. Chen and Chvátal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this work, we prove a slightly stronger version of Chen and Chvátal conjecture for a family of graphs containing chordal graphs and distance‐hereditary graphs.     

On a conjecture of Hoàng and Tu concerning perfectly orderable graphs

Hoàng and Tu [On the perfect orderability of unions of two graphs, J. Graph Theory 33 (2000) 32-43] conjectured that a weakly triangulated graph which does not contain a chordless path with six vertices is perfectly orderable. We present a counter example to this conjecture.     

On the perfect orderability of unions of two graphs

A graph G is perfectly orderable, if it admits an order < on its vertices such that the sequential coloring algorithm delivers an optimum coloring on each induced subgraph (H, <) of (G, <). A graph is a threshold graph, if it contains no P₄, 2K₂, and C₄ as induced subgraph. A theorem of Chvátal, Hoàng, Mahadev, and de Werra states that a graph is perfectly orderable, if it is the union of two threshold graphs. In this article, we investigate possible generalizations of the above theorem. Hoàng has conjectured that, if G is the union of two graphs G₁ and G₂, then G is perfectly orderable whenever G₁ and G₂ are both P₄‐free and 2K₂‐free. We show that the complement of the chordless cycle with at least five vertices cannot be a counter‐example to this conjecture, and we prove a special case of it: if G₁ and G₂ are two edge‐disjoint graphs that are P₄‐free and 2K₂‐free, then the union of G₁ and G₂ is perfectly orderable. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 32–43, 2000     

Four classes of perfectly orderable graphs

A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F, a certain “greedy” coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.     

On the structure of bull-free perfect graphs

A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. Chvátal and Sbihi showed that the Strong Perfect Graph Conjecture holds for bull-free graphs. We show that bull-free perfect graphs are quasi-parity graphs, and that bull-free perfect graphs with no antihole are perfectly contractile. Our proof yields a polynomial algorithm for coloring bull-free strict quasi-parity graphsPartially supported by CNPq, grant 30 1160/91.0     

Toughness, hamiltonicity and split graphs

Related to Chvátal's famous conjecture stating that every 2-tough graph is hamiltonian, we study the relation of toughness and hamiltonicity on special classes of graphs.

First, we consider properties of graph classes related to hamiltonicity, traceability and toughness concepts and display some algorithmic consequences. Furthermore, we present a polynomial time algorithm deciding whether the toughness of a given split graph is less than one and show that deciding whether the toughness of a bipartite graph is exactly one is coNP-complete.

We show that every split graph is hamiltonian and that there is a sequence of non-hamiltonian split graphs with toughness converging to .     

Proof of Ding’s conjecture on maximal stable sets and maximal cliques in planar graphs

X. Deng et al. proved Chvātal＇s conjecture on maximal stable sets and maximal cliques in graphs. G. Ding made a conjecture to generalize Chvátal＇s conjecture. The purpose of this paper is to prove this conjecture in planar graphs and the complement of planar graphs.     

Equistable graphs, general partition graphs, triangle graphs, and graph products

In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.     

On Toughness and Hamiltonicity of 2K2‐Free Graphs

The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A whose removal yields components. Determining toughness is an NP‐hard problem for general input graphs. The toughness conjecture of Chvátal, which states that there exists a constant t such that every graph on at least three vertices with toughness at least t is hamiltonian, is still open for general graphs. We extend some known toughness results for split graphs to the more general class of 2K₂‐free graphs, that is, graphs that do not contain two vertex‐disjoint edges as an induced subgraph. We prove that the problem of determining toughness is polynomially solvable and that Chvátal's toughness conjecture is true for 2K₂‐free graphs.     

Perfectly orderable graphs and almost all perfect graphs are kernelM-solvable

A graph is perfectly orderable if and only if it admits an acyclic orientation which does not contain an induced subgraph with verticesa, b, c, d and arcsab, bc, dc. Further a graph is called kernelM-solvable if for every direction of the edges (here pairs of symmetric, i.e. reversible, arcs are allowed) such that every directed triangle possesses at least two pairs of symmetric arcs, there exists a kernel, i.e. an independent setK of vertices such that every other vertex sends some arc towardsK. We prove that perfectly orderable graphs are kernelM-solvable. Using a deep result of Prömel and Steger we derive that almost all perfect graphs are kernelM-solvable.     

Tolerance graphs

Tolerance graphs arise from the intersection of intervals with varying tolerances in a way that generalizes both interval graphs and permutation graphs. In this paper we prove that every tolerance graph is perfect by demonstrating that its complement is perfectly orderable. We show that a tolerance graph cannot contain a chordless cycle of length greater than or equal to 5 nor the complement of one. We also discuss the subclasses of bounded tolerance graphs, proper tolerance graphs, and unit tolerance graphs and present several possible applications and open questions.     

Most unbreakable murky graphs are bull-free

A bull is the (self-complementary) graph with nodesa, b, c, d, e and edgesab, ac, bc, bd,ce. A star cutset in a graph G is a set C of nodes such thatG-C is disconnected, and such that some node inC is adjacent to all remaining nodes inC. A graph is called unbreakable if it has more than two nodes and if neither the graph nor its complement has a star cutset. Hayward defined a graphG to be murky if neitherG nor its complement contains a chordless cycle with five nodes or a chordless path with six nodes. We prove that most unbreakable murky graphs are bull-free. This leads, via a result of Chvátal and Sbihi, to a shortening of Hayward’s proof that murky graphs are perfect.     

Non-intersecting perfect matchings in cubic graphs (Extended abstract)

A conjecture of G. Fan and A. Raspaud asserts that every bridgeless cubic graph contains three perfect matchings with empty intersection. We suggest a possible approach to problems of this type, based on the concept of a balanced join in an embedded graph. The method can be used to prove a special case of a conjecture of E. Máčajová and M. Škoviera on Fano colorings of cubic graphs.     

Representing edge intersection graphs of paths on degree 4 trees

Let P be a collection of nontrivial simple paths on a host tree T. The edge intersection graph of P, denoted by EPT(P), has vertex set that corresponds to the members of P, and two vertices are joined by an edge if and only if the corresponding members of P share at least one common edge in T. An undirected graph G is called an edge intersection graph of paths in a tree if G=EPT(P) for some P and T. The EPT graphs are useful in network applications. Scheduling undirected calls in a tree network or assigning wavelengths to virtual connections in an optical tree network are equivalent to coloring its EPT graph.An undirected graph G is chordal if every cycle in G of length greater than 3 possesses a chord. Chordal graphs correspond to vertex intersection graphs of subtrees on a tree. An undirected graph G is weakly chordal if every cycle of length greater than 4 in G and in its complement possesses a chord. It is known that the EPT graphs restricted to host trees of vertex degree 3 are precisely the chordal EPT graphs. We prove a new analogous result that weakly chordal EPT graphs are precisely the EPT graphs with host tree restricted to degree 4. Moreover, this provides an algorithm to reduce a given EPT representation of a weakly chordal EPT graph to an EPT representation on a degree 4 tree. Finally, we raise a number of intriguing open questions regarding related families of graphs.     

Connected matchings in chordal bipartite graphs

A connected matching in a graph is a collection of edges that are pairwise disjoint but joined by another edge of the graph. Motivated by applications to Hadwiger’s conjecture, Plummer, Stiebitz, and Toft (2003) introduced connected matchings and proved that, given a positive integer $k$, determining whether a graph has a connected matching of size at least $k$ is NP-complete. Cameron (2003) proved that this problem remains NP-complete on bipartite graphs, but can be solved in polynomial-time on chordal graphs. We present a polynomial-time algorithm that finds a maximum connected matching in a chordal bipartite graph. This includes a novel edge-without-vertex-elimination ordering of independent interest. We give several applications of the algorithm, including computing the Hadwiger number of a chordal bipartite graph, solving the unit-time bipartite margin-shop scheduling problem in the case in which the bipartite complement of the precedence graph is chordal bipartite, and determining–in a totally balanced binary matrix–the largest size of a square sub-matrix that is permutation equivalent to a matrix with all zero entries above the main diagonal.     

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.     

On the complexity of recognizing perfectly orderable graphs

The question whether a polynomial time recognition algorithm for the class of perfectly orderable graphs exists was posed by Chvátal in 1981 when he introduced the notion of perfect orders. Since then several classes of perfectly orderable graphs have been identified. In this note we prove that recognizing perfectly orderable graphs is NP-complete.