Approximately Coloring Graphs Without Long Induced Paths
Tóm tắt
It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable graph without an induced path on t vertices, computes a coloring with
$$\max \left\{ 5,2\left\lceil \frac{t-1}{2}\right\rceil -2\right\} $$
many colors. If the input graph is triangle-free, we only need
$$\max \left\{ 4,\left\lceil \frac{t-1}{2}\right\rceil +1\right\} $$
many colors. The running time of our algorithm is
$$O((3^{t-2}+t^2)m+n)$$
if the input graph has n vertices and m edges.
Từ khóa
Tài liệu tham khảo
Brakensiek, J., Guruswami, V.: New hardness results for graph and hypergraph colorings. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 50. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)
Bonomo, F., Chudnovsky, M., Maceli, P., Schaudt, O., Stein, M., Zhong, M.: Three-coloring and list three-coloring graphs without induced paths on seven vertices. Combinatorica 38(4), 779–801 (2018)
Chlamtac, E.: Approximation algorithms using hierarchies of semidefinite programming relaxations. In: 48th Annual IEEE Symposium on Foundations of Computer Science (2007)
Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring \(P_6\)-free graphs. I. Extending an excellent precoloring. arXiv preprint arXiv:1802.02282 (2018)
Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring \(P_6\)-free graphs. II. Finding an excellent precoloring. arXiv preprint arXiv:1802.02283 (2018)
Chuzhoy, J.: Private communication (2015)
Dinur, I., Mossel, E., Regev, O.: Conditional hardness for approximate coloring. SIAM J. Comput. 39, 843–873 (2009)
Edwards, K.: The complexity of colouring problems on dense graphs. Theor. Comput. Sci. 43, 337–343 (1986)
Erdős, P., Rubin, A.L., Taylor, H.: Choosability in graphs. Congressus Numerantium 26, 125–157 (1979)
Garey, M.R., Johnson, D.S.: A Guide to the Theory of NP-Completeness. WH Freemann, New York (1979)
Groenland, C., Okrasa, K., Rzążewski, P., Scott, A., Seymour, P., Spirkl, S.: \( H \)-colouring \( P_t \)-free graphs in subexponential time. arXiv preprint arXiv:1803.05396 (2018)
Golovach, P.A., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of colouring graphs with forbidden subgraphs. J. Graph Theory 84(4), 331–363 (2017)
Gyárfás, A.: Problems from the world surrounding perfect graphs. Appl. Math. 19(3–4), 413–441 (1987)
Hoàng, C.T., Kamiński, M., Lozin, V., Sawada, J., Shu, X.: Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time. Algorithmica 57(1), 74–81 (2010)
Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10, 718–720 (1981)
Huang, S.: Improved complexity results on \(k\)-coloring \(P_t\)-free graphs. Eur. J. Comb. 51, 336–346 (2016)
Huang, S., Johnson, M., Paulusma, D.: Narrowing the complexity gap for colouring \((C_s, P_t)\)-free graphs. Comput. J. 58(11), 3074–3088 (2015)
Kamiński, M., Lozin, V.: Coloring edges and vertices of graphs without short or long cycles. Contrib. Discrete Math. 2, 61–66 (2007)
Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
Kawarabayashi, K., Thorup, M.: Coloring 3-Colorable Graphs with \(o (n^{1/5})\) Colors. LIPIcs-Leibniz International Proceedings in Informatics, vol. 25. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern (2014)
Král, D., Kratochvíl, J., Tuza, Z., Woeginger, G.J.: Complexity of coloring graphs without forbidden induced subgraphs. Proc. WG 2001, 254–262 (2001)
Leven, D., Galil, Z.: NP-completeness of finding the chromatic index of regular graphs. J. Algorithms 4, 35–44 (1983)
Vizing, V.G.: Coloring the vertices of a graph in prescribed colors. Diskret. Analiz 29(3), 3–10 (1976)