Coloring Artemis graphs. (English) Zbl 1165.05027
Summary: We consider the class of graphs that contain no odd hole, no antihole, and no “prism” (a graph consisting of two disjoint triangles with three disjoint paths between them). We give an algorithm that can optimally color the vertices of these graphs in time \(O(n^{2}m)\).
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C15 | Coloring of graphs and hypergraphs |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Berge, C., Les problèmes de coloration en théorie des graphes, Publ. Inst. Stat. Univ. Paris, 9, 123-160 (1960) · Zbl 0103.16201 |
| [2] | Bertschi, M. E., Perfectly contractile graphs, J. Combin. Theory Ser. B, 50, 222-230 (1990) · Zbl 0727.05024 |
| [3] | Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R., The strong perfect graph theorem, Ann. Math., 164, 51-229 (2006) · Zbl 1112.05042 |
| [4] | Chudnovsky, M.; Seymour, P., Even pairs in Berge graphs, J. Combin. Theory Ser. B, 99, 370-377 (2009) · Zbl 1227.05152 |
| [5] | Chvátal, V.; Chvátal, Perfectly ordered graphs, (Berge, C., Topics on Perfect Graphs. Topics on Perfect Graphs, Ann. Disc. Math., vol. 21 (1984), North Holland: North Holland Amsterdam), 63-68 · Zbl 0559.05055 |
| [6] | Everett, H.; de Figueiredo, C. M.H.; Linhares Sales, C.; Maffray, F.; Porto, O.; Reed, B. A., Even pairs, (Ramírez-Alfonsín, J. L.; Reed, B. A., Perfect Graphs (2001), Wiley Interscience), 67-92 · Zbl 0990.05053 |
| [7] | Fonlupt, J.; Uhry, J. P., Transformations which preserve perfectness and \(h\)-perfectness of graphs, Ann. Discrete Math., 16, 83-85 (1982) · Zbl 0502.05023 |
| [8] | Grötschel, M.; Lovász, L.; Schrijver, A., Polynomial algorithms for perfect graphs, (Topics on Perfect Graphs. Topics on Perfect Graphs, North-Holland Math. Stud., vol. 88 (1984), North-Holland: North-Holland Amsterdam, New York), 325-356 · Zbl 0554.05041 |
| [9] | Hayward, R. B., Weakly triangulated graphs, J. Combin. Theory Ser. B, 39, 200-208 (1985) · Zbl 0551.05055 |
| [10] | Hayward, R. B., Meyniel weakly triangulated graphs I: Co-perfect orderability, Discrete Appl. Math., 73, 199-210 (1997) · Zbl 0878.05035 |
| [11] | Hayward, R. B., Meyniel weakly triangulated graphs II: A theorem of Dirac, Discrete Appl. Math., 78, 283-289 (1997) · Zbl 0885.05080 |
| [12] | R.B. Hayward, J.P. Spinrad, R. Sritharan, Weakly chordal graph algorithms via handles, in: Proc.11th Annual ACM-SIAM Symp. on Discrete Algorithms, 2000, pp. 42-49; R.B. Hayward, J.P. Spinrad, R. Sritharan, Weakly chordal graph algorithms via handles, in: Proc.11th Annual ACM-SIAM Symp. on Discrete Algorithms, 2000, pp. 42-49 · Zbl 0956.68104 |
| [13] | Hayward, R. B.; Spinrad, J. P.; Sritharan, R., Improved algorithms for weakly chordal graphs, ACM Trans. Algorithms, 3, 2 (2007), article 14 · Zbl 1321.05265 |
| [14] | Jost, V.; Lévêque, B.; Maffray, F., Precoloring extension of co-Meyniel graphs, Graphs Combin., 23, 291-301 (2007) · Zbl 1123.05038 |
| [15] | Karapetian, I. A.; Markossian, S. E., Perfect graphs, Akad. Nauk Armenii Dokl., 63, 292-296 (1976), (in Russian) · Zbl 0357.05063 |
| [16] | Maffray, F.; Trotignon, N., A class of perfectly contractile graphs, J. Combin. Theory Ser. B, 96, 1-19 (2006) · Zbl 1078.05034 |
| [17] | Maffray, F.; Trotignon, N., Algorithms for perfectly contractile graphs, SIAM J. Discrete Math., 19, 553-574 (2005) · Zbl 1094.05028 |
| [18] | Meyniel, H., On the perfect graph conjecture, Discrete Math., 16, 339-342 (1976) · Zbl 0383.05018 |
| [19] | Middendorf, M.; Pfeiffer, F., On the complexity of recognizing perfectly orderable graphs, Discrete Math., 80, 327-333 (1990) · Zbl 0706.68058 |
| [20] | Raghavan, V.; Spinrad, J., Robust algorithms for restricted domains, J. Algorithms, 48, 160-172 (2003) · Zbl 1079.68110 |
| [21] | B.A. Reed, Problem session on parity problems (Public communication), in: DIMACS Workshop on Perfect Graphs, Princeton Univ., New Jersey, 1993; B.A. Reed, Problem session on parity problems (Public communication), in: DIMACS Workshop on Perfect Graphs, Princeton Univ., New Jersey, 1993 |
| [22] | Roussel, F.; Rusu, I., An \(O(n^2)\) algorithm to color Meyniel graphs, Discrete Math., 235, 107-123 (2001) · Zbl 0978.05033 |
| [23] | N. Trotignon, Graphes parfaits: Structure et algorithmes. Doctoral Thesis, University Joseph Fourier, Grenoble, France, 2004; N. Trotignon, Graphes parfaits: Structure et algorithmes. Doctoral Thesis, University Joseph Fourier, Grenoble, France, 2004 |
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.
