Registro:

Referencias:

• Aspvall, B., Plass, M.F., Tarjan, R.E., A linear-time algorithm for testing the truth of certain quantified boolean formulas (1979) Information Processing Letters, 8, pp. 121-123
• Camby, E., Schaudt, O., A new characterization of Pk-free graphs (2014) Algorithmica
• Chudnovsky, M., Maceli, P., Stacho, J., Zhong, M., (2014) 4-coloring P6-free graphs with no induced 5-cycles
• Coppersmith, D., Winograd, S., Matrix multiplication via arithmetic progressions (1990) J. Symbolic Computation, 9, pp. 251-280
• Corneil, D., Perl, Y., Stewart, L., Cographs: recognition (1984) applications and algorithms, Congressus Numerantium, 43, pp. 249-258
• Edwards, K., The complexity of colouring problems on dense graphs (1986) Theoretical Computer Science, 43, pp. 337-343
• Erdos, P., Rubin, A., Taylor, H., Choosability in graphs (1979) Congressus Numerantium, 26, pp. 125-157
• Golovach, P., Johnson, M., Paulusma, D., Song, J., (2015) A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
• Golovach, P., Paulusma, D., Song, J., Closing complexity gaps for coloring problems on H-free graphs (2014) Information and Computation, 237, pp. 204-214
• Hell, P., Huang, S., (2013) Complexity of coloring graphs without paths and cycles
• Hoàng, C.T., Kaminski, M., Lozin, V.V., Sawada, J., Shu, X., Deciding k-colorability of P5-free graphs in polynomial time (2010) Algorithmica, 57, pp. 74-81
• Holyer, I., The NP-completeness of edge-coloring (1981) SIAM Journal on Computing, 10, pp. 718-720
• Huang, S., Improved complexity results on k-coloring Pt-free graphs (2013) Proceedings of the International Symposium on Mathematical Foundations of Computer Science 2013, pp. 551-558
• Huang, S., Johnson, M., Paulusma, D., (2014) Narrowing the complexity gap for colouring (Cs,Pt)-free graphs
• Kaminski, M., Lozin, V.V., Coloring edges and vertices of graphs without short or long cycles (2007) Contributions to Discrete Mathematics, 2, pp. 61-66
• Karp, R., Reducibility among combinatorial problems (1972) Complexity of Computer Computations, pp. 85-103. , Miller R., Thatcher J., (eds), Plenum Press, New York
• Král, D., Kratochvíl, J., Tuza, Z., Woeginger, G.J., Complexity of coloring graphs without forbidden induced subgraphs (2001) Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science 2001, pp. 254-262. , Golumbic M. C., Stern M., Levy A., Morgenstern G., (eds
• Leven, D., Galil, Z., NP-completeness of finding the chromatic index of regular graphs (1983) Journal of Algorithms, 4, pp. 35-44
• Maffray, F., Preissmann, M., On the NP-completeness of the k-colorability problem for triangle-free graphs (1996) Discrete Mathematics, 162, pp. 313-317
• Mellin, S., (2002) Polynomielle farbungsalgorithmen für Pk-freie graphen
• Randerath, B., Schiermeyer, I., 3-Colorability 2 P for P6-free graphs (2004) Discrete Applied Mathematics, 136, pp. 299-313
• Randerath, B., Schiermeyer, I., Tewes, M., Three-colorability and forbidden subgraphs. II: polynomial algorithms (2002) Discrete Mathematics, 251, pp. 137-153
• Stacho, J., (2014) Personal communication
• Stockmeyer, L., Planar 3-colorability is polynomial complete (1973) ACM SIGACT News, 5, pp. 19-25
• Tuza, Z., Graph colorings with local constraints–a survey (1997) Discussiones Mathematicae. Graph Theory, 17, pp. 161-228
• Vizing, V., Coloring the vertices of a graph in prescribed colors (1976) Metody Diskretnogo Analiza, 29, pp. 3-10

Citas:

---------- APA ----------

---------- CHICAGO ----------

---------- MLA ----------

---------- VANCOUVER ----------