Abstract:
In this paper we present a polynomial time algorithm that determines if an input graph containing no induced seven-vertex path is 3-colorable. This affirmatively answers a question posed by Randerath, Schiermeyer and Tewes in 2002. Our algorithm also solves the list-coloring version of the 3-coloring problem, where every vertex is assigned a list of colors that is a subset of {1,2,3}, and gives an explicit coloring if one exists. © 2018, János Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature.
Registro:
Documento: |
Artículo
|
Título: | Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices |
Autor: | Bonomo, F.; Chudnovsky, M.; Maceli, P.; Schaudt, O.; Stein, M.; Zhong, M. |
Filiación: | CONICET and Departamento de Computación, FCEN, Universidad de Buenos Aires, Aires, Argentina Princeton University, Princeton, NJ 08544, United States Department of Mathematics and Statistics, Canisius College, Buffalo, NY 14208, United States Institut für Informatik, Universität zu Käln, Käln, Germany Departamento de Ingeniería Matemática, Universidad de Chile, Santiago, Chile Columbia University, New York, NY 10027, United States
|
Año: | 2018
|
Volumen: | 38
|
Número: | 4
|
Página de inicio: | 779
|
Página de fin: | 801
|
DOI: |
http://dx.doi.org/10.1007/s00493-017-3553-8 |
Título revista: | Combinatorica
|
Título revista abreviado: | Combinatorica
|
ISSN: | 02099683
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02099683_v38_n4_p779_Bonomo |
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 ----------
Bonomo, F., Chudnovsky, M., Maceli, P., Schaudt, O., Stein, M. & Zhong, M.
(2018)
. Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices. Combinatorica, 38(4), 779-801.
http://dx.doi.org/10.1007/s00493-017-3553-8---------- CHICAGO ----------
Bonomo, F., Chudnovsky, M., Maceli, P., Schaudt, O., Stein, M., Zhong, M.
"Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices"
. Combinatorica 38, no. 4
(2018) : 779-801.
http://dx.doi.org/10.1007/s00493-017-3553-8---------- MLA ----------
Bonomo, F., Chudnovsky, M., Maceli, P., Schaudt, O., Stein, M., Zhong, M.
"Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices"
. Combinatorica, vol. 38, no. 4, 2018, pp. 779-801.
http://dx.doi.org/10.1007/s00493-017-3553-8---------- VANCOUVER ----------
Bonomo, F., Chudnovsky, M., Maceli, P., Schaudt, O., Stein, M., Zhong, M. Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices. Combinatorica. 2018;38(4):779-801.
http://dx.doi.org/10.1007/s00493-017-3553-8