×

On the structure of bull-free perfect graphs. (English) Zbl 0869.05028

An even pair of a graph is any pair of vertices such that every chordless path between them has even length. A graph is called a quasi-parity graph if every non-trivial induced subgraph either has an even pair or its complement has an even pair. H. Meyniel proved that every quasi-parity graph is perfect [Eur. J. Comb. 8, 313-316 (1987; Zbl 0647.05053)].
Given a graph \(G\) and an even pair \(x\), \(y\) of \(G\), the contraction of the two vertices \(x\), \(y\) is denoted by \(G/xy\). A graph is called perfectly contractile if for every induced subgraph \(H\) there exists a sequence \(H_{0},\ldots ,H_{p}\) of graphs such that: \(H=H_{0}\); \(H_{i}\) has an even pair \(x_{i}\), \(y_{i}\) for \(i=0,\ldots ,p-1\); \(H_{i+1}=H_{i}/x_{i}y_{i}\); and \(H_{p}\) is a clique. A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. V. Chvátal and N. Sbihi showed that the strong perfect graph conjecture holds for bull-free graphs [Graph. Comb. 3, 127-139 (1987; Zbl 0633.05056)].
In this paper it is shown that bull-free perfect graphs are quasi-parity graphs, and that bull-free perfect graphs with no antihole are perfectly contractile. The proof yields a polynomial algorithm for coloring bull-free strict quasi-parity graphs with \(n\) vertices and \(m\) edges with complexity \(O(n^{4}m)\). Some conjectures and open problems conclude the paper.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C.: Les problèmes de coloration en théorie des graphes. Publ. Inst. Stat. Univ. Paris9, 123-160 (1960) · Zbl 0103.16201
[2] Bertschi, M.E.: Perfectly contractile graphs. J. Comb. Theory Ser.B 50, 222-230 (1990) · Zbl 0727.05024 · doi:10.1016/0095-8956(90)90077-D
[3] Chvátal, V.: Perfectly ordered graphs. In Berge C. and V. Chvátal, editors, Topics on Perfect Graphs, pages 63-65. North-Holland. Amsterdam, 1984 · Zbl 0559.05055
[4] Chvátal, V.: A class of perfectly orderable graphs. Technical Report 89573-OR, Forschungsbereich für Diskrete Mathematik, Institut für Ökonometrie und Operations Research, Rheinische Friedrich Wilhelms Universitaet, Bonn, Germany, May 1989
[5] Chvátal, V., Sbihi, N.: Bull-free Berge graphs are perfect. Graph. Comb.3, 127-139 (1987) · Zbl 0633.05056 · doi:10.1007/BF01788536
[6] Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput.14, 926-934 (1985) · Zbl 0575.68065 · doi:10.1137/0214065
[7] De Figueiredo, C.M.H.: Um Estudo de Problemas Combinatórios em Grafos Perfeitos. PhD thesis, COPPE/UFRJ, Rio de Janeiro, 1991. In Portuguese
[8] Fonlupt, J., Uhry, J.P.: Transformations which preserve perfectness andh-perfectness of graphs. Annals of Disc. Math.16, 83-85 (1982) · Zbl 0502.05023
[9] Grötschel, M., Lovász, L., Schrijver, A.: Polynomial algorithms for perfect graphs. In C. Berge and V. Chvátal, editors, Topics on Perfect Graphs (Ann. Discrete Math. 21), pages 325-356. North-Holland, Amsterdam, 1984 · Zbl 0554.05041
[10] Hayward, R.: Weakly triangulated graphs. J. Comb. Theory Ser.B 39, 200-209 (1985) · Zbl 0551.05055 · doi:10.1016/0095-8956(85)90050-4
[11] Hayward, R., Hoàng, C.T., Maffray, F.: Optimizing weakly triangulated graphs. Graph. Comb.5, 339-349 (1989). See erratum in vol. 6, 1990, p. 33-35 · Zbl 0679.68082 · doi:10.1007/BF01788689
[12] Hertz, A., de Werra, D.: Perfectly orderable graphs are quasi-parity graphs: a short proof. Disc. Math.68, 111-113 (1988) · Zbl 0632.05049 · doi:10.1016/0012-365X(88)90047-7
[13] Hoàng, C.T.: Algorithms for minimum weighted coloring of perfectly ordered, comparability, triangulated and clique-separable graphs. Technical Report 90832, Forschungsinstitut für Diskrete Mathematik, Institut für Operations Research, Universitaet Bonn, Germany, March 1990. Disc. Appl. Math. (to be published)
[14] Meyniel, H.: A new property of critical imperfect graphs and some consequences. Europ. J. Comb.8, 313-316 (1987) · Zbl 0647.05053
[15] Reed, B.A.: Problem session on parity problems. Perfect Graphs Workshop, Princeton University, New Jersey, June 1993
[16] Reed, B.A., Sbihi, N.: Recognizing bull-free perfect graphs. preprint, 1990 · Zbl 0832.05039
[17] Seinsche, S.: On a property of the class ofn-colorable graphs. J. Comb. Theory Ser. B16, 191-193 (1974) · Zbl 0269.05103 · doi:10.1016/0095-8956(74)90063-X
[18] Spinrad, J.:P 4-trees and substitution decomposition. Disc. Appl. Math.39, 263-291 (1992) · Zbl 0758.68036 · doi:10.1016/0166-218X(92)90180-I
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.