zbMATH — the first resource for mathematics

Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time. (English) Zbl 1222.68083
Summary: The problem of computing the chromatic number of a \(P_5\)-free graph (a graph which contains no path on 5 vertices as an induced subgraph) is known to be NP-hard. However, we show that for every fixed integer \(k\), there exists a polynomial-time algorithm determining whether or not a \(P_5\)-free graph admits a \(k\)-coloring, and finding one, if it does.

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX Cite
Full Text: DOI
[1] Bacsó, G., Tuza, Z.: Dominating cliques in P 5-free graphs. Period. Math. Hung. 21(4), 303–308 (1990) · Zbl 0746.05065
[2] Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251–280 (1990) · Zbl 0702.65046
[3] Diestel, R.: Graph Theory, electronic edn. (2005) · Zbl 1074.05001
[4] de Werra, D., Kobler, D.: Graph coloring: foundations and applications. RAIRO Oper. Res. 37, 29–66 (2003) · Zbl 1062.90026
[5] Even, S., Pnueli, A., Lempel, A.: Permutation graphs and transitive graphs. J. Assoc. Comput. Mach. 19, 400–410 (1972) · Zbl 0251.05113
[6] Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum coloring by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1, 180–187 (1972) · Zbl 0227.05116
[7] Giakoumakis, V., Rusu, I.: Weighted parameters in \((P_{5},\overline{P}_{5})\) -free graphs. Discrete Appl. Math. 80, 255–261 (1997) · Zbl 0903.05045
[8] Grötschel, M., Lovász, L., Schrijver, A.: Polynomial algorithms for perfect graphs. Ann. Discrete Math. 21, 325–356 (1984) · Zbl 0554.05041
[9] Hayward, R., Hoàng, C.T., Maffray, F.: Optimizing weakly triangulated graphs. Graphs Comb. 5, 339–349 (1989) · Zbl 0679.68082
[10] Hoàng, C.T., Sawada, J., Wang, Z.: Colorability of P 5-free graphs. Manuscript (2005)
[11] Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10, 718–720 (1981) · Zbl 0473.68034
[12] Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)
[13] Khanna, S., Linial, N., Safra, S.: On the hardness of approximating the chromatic number. Combinatorica 20, 393–415 (2000) · Zbl 0964.68065
[14] Korobitsyn, D.V.: On the complexity of determining the domination number in monogenic classes of graphs. Diskret. Mat. 2(3), 90–96 (1990) (in Russian); translation in Discrete Math. Appl. 2(2), 191–199 (1992) · Zbl 0729.05047
[15] Kral, D., Kratochvil, J., Tuza, Z., Woeginger, G.J.: Complexity of coloring graphs without forbidden induced subgraphs. In: WG 2001. Lecture Notes in Computer Science, vol. 2204, pp. 254–262. Springer, Berlin (2001) · Zbl 1042.68639
[16] Bang Le, V., Randerath, B., Schiermeyer, I.: Two remarks on coloring graphs without long induced paths. Report No. 7/2006 (Algorithmic Graph Theory), Mathematisches Forschungsinstitut Oberwolfach · Zbl 1143.68060
[17] Maffray, F., Preissmann, M.: On the NP-completeness of the k-colorability problem for triangle-free graphs. Discrete Math. 162, 313–317 (1996) · Zbl 0870.05021
[18] Randerath, B., Schiermeyer, I.: Vertex coloring and forbidden subgraphs–a survey. Graphs Comb. 20(1), 1–40 (2004) · Zbl 1056.05065
[19] Randerath, B., Schiermeyer, I.: 3-colorability for P 6-free graphs. Discrete Appl. Math. 136, 299–313 (2004) · Zbl 1035.05042
[20] Randerath, B., Schiermeyer, I., Tewes, M.: Three-colorability and forbidden subgraphs, II: polynomial algorithms. Discrete Math. 251, 137–153 (2002) · Zbl 0999.05042
[21] Sgall, J., Woeginger, G.J.: The complexity of coloring graphs without long induced paths. Acta Cybern. 15(1), 107–117 (2001) · Zbl 0981.05037
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.