Three-coloring and list three-coloring of graphs without induced paths on seven vertices
2018, Combinatorica 38 (4), 779-801, 2018Citas: 95
Agregar PDF Importar citas Plots Conexiones
Autor(es)
Flavia Bonomo and Maria Chudnovsky and Peter Maceli and Oliver Schaudt and Maya Stein and Mingxian Zhong
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.
Plot de citas
Citas de Scrapping
| # | Año | #Citas | Título | Autores | Journal | Editor |
|---|---|---|---|---|---|---|
| 1 | 2017 | 140 | A survey on the computational complexity of coloring graphs with forbidden subgraphs | PA Golovach, M Johnson, D Paulusma… - Journal of Graph …, 2017 - Wiley Online Library | ||
| 2 | 2023 | 1 | MIP formulations for induced graph optimization problems: a tutorial | RA Melo, CC Ribeiro - International Transactions in …, 2023 - Wiley Online Library | ||
| 3 | 2021 | 35 | Quasi-polynomial-time algorithm for Independent Set in Pt-free graphs via shrinking the space of induced paths | M Pilipczuk, M Pilipczuk, P Rzążewski - Symposium on Simplicity in Algorithms …, 2021 - SIAM | ||
| 4 | 2019 | 50 | Four-coloring P6-free graphs | M Chudnovsky, S Spirkl, M Zhong - Proceedings of the Thirtieth Annual ACM …, 2019 - SIAM | ||
| 5 | 2019 | 40 | Independent Feedback Vertex Set for -Free Graphs | M Bonamy, KK Dabrowski, C Feghali, M Johnson… - Algorithmica, 2019 - Springer | ||
| 6 | 2023 | 5 | A refinement on the structure of vertex-critical (P5, gem)-free graphs | B Cameron, CT Hoàng - Theoretical Computer Science, 2023 - Elsevier | ||
| 7 | 2024 | 5 | Infinite Families of k-Vertex-Critical (, )-Free Graphs | B Cameron, C Hoàng - Graphs and Combinatorics, 2024 - Springer | ||
| 8 | 2204 | 9 | On coloring of graphs of girth 2l+ 1 without longer odd holes | D Wu, B Xu, Y Xu - arXiv preprint arXiv:2204.06284, 2022 - arxiv.org | ||
| 9 | 2020 | 26 | Colouring (Pr + Ps)-Free Graphs | T Klimošová, J Malík, T Masařík, J Novotná… - Algorithmica, 2020 - Springer | ||
| 10 | 2019 | 27 | H-colouring Pt-free graphs in subexponential time | C Groenland, K Okrasa, P Rzążewski, A Scott… - Discrete Applied …, 2019 - Elsevier | ||
| 11 | 2021 | 13 | Finding Large -Colorable Subgraphs in Hereditary Graph Classes | M Chudnovsky, J King, M Pilipczuk… - SIAM Journal on Discrete …, 2021 - SIAM | ||
| 12 | 2017 | 32 | Colouring diamond-free graphs | KK Dabrowski, F Dross, D Paulusma - Journal of computer and system …, 2017 - Elsevier | ||
| 13 | 2022 | 12 | List k-colouring Pt-free graphs: A mim-width perspective | N Brettell, J Horsfield, A Munaro, D Paulusma - Information Processing …, 2022 - Elsevier | ||
| 14 | 2022 | 7 | New formulations and branch-and-cut procedures for the longest induced path problem | RG Marzo, RA Melo, CC Ribeiro, MC Santos - Computers & Operations …, 2022 - Elsevier | ||
| 15 | 2022 | 8 | Complexity dichotomy for list-5-coloring with a forbidden induced subgraph | S Hajebi, Y Li, S Spirkl - SIAM Journal on Discrete Mathematics, 2022 - SIAM | ||
| 16 | 2019 | 16 | Colouring H-free graphs of bounded diameter | B Martin, D Paulusma, S Smith, P Rossmanith… - 2019 - durham-repository.worktribe.com | ||
| 17 | 2024 | 4 | Vertex-critical (P3+ ℓP1)-free and vertex-critical (gem, co-gem)-free graphs | T Abuadas, B Cameron, CT Hoàng… - Discrete Applied …, 2024 - Elsevier | ||
| 18 | 2020 | 12 | List 3-coloring Pt-free graphs with no induced 1-subdivision of K1, s | M Chudnovsky, S Spirkl, M Zhong - Discrete Mathematics, 2020 - Elsevier | ||
| 19 | 2020 | 23 | Obstructions for three-coloring graphs without induced paths on six vertices | M Chudnovsky, J Goedgebeur, O Schaudt… - Journal of Combinatorial …, 2020 - Elsevier | ||
| 20 | 2021 | 10 | k-critical graphs in P5-free graphs | K Cameron, J Goedgebeur, S Huang, Y Shi - Theoretical Computer Science, 2021 - Elsevier | ||
| 21 | 2021 | 12 | List 3-Coloring Graphs with No Induced | M Chudnovsky, S Huang, S Spirkl, M Zhong - Algorithmica, 2021 - Springer | ||
| 22 | 2019 | 15 | Colouring square-free graphs without long induced paths | S Gaspers, S Huang, D Paulusma - Journal of Computer and System …, 2019 - Elsevier | ||
| 23 | 2021 | 8 | Colouring graphs of bounded diameter in the absence of small cycles | B Martin, D Paulusma, S Smith - … , CIAC 2021, Virtual Event, May 10–12 …, 2021 - Springer | ||
| 24 | 2022 | 7 | Colouring graphs of bounded diameter in the absence of small cycles | B Martin, D Paulusma, S Smith - Discrete Applied Mathematics, 2022 - Elsevier | ||
| 25 | 2023 | 9 | Complexity of Ck-coloring in hereditary classes of graphs | M Chudnovsky, S Huang, P Rzążewski, S Spirkl… - Information and …, 2023 - Elsevier | ||
| 26 | 2022 | 2 | Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws | M Dębski, Z Lonc, K Okrasa, M Piecyk… - arXiv preprint arXiv …, 2022 - arxiv.org | ||
| 27 | 2021 | 8 | On List k-Coloring Convex Bipartite Graphs | J Díaz, ÖY Diner, M Serna, O Serra - Graphs and Combinatorial …, 2021 - Springer | ||
| 28 | 2018 | 12 | 3-Colorable Subclasses of -Free Graphs | M Chudnovsky, J Stacho - SIAM Journal on Discrete Mathematics, 2018 - SIAM | ||
| 29 | 2010 | 6 | Complexity of the list homomorphism problem in hereditary graph classes | K Okrasa, P Rzążewski - arXiv preprint arXiv:2010.03393, 2020 - arxiv.org | ||
| 30 | 2017 | 19 | 4‐Coloring P6‐Free Graphs with No Induced 5‐Cycles | M Chudnovsky, P Maceli, J Stacho… - Journal of Graph …, 2017 - Wiley Online Library | ||
| 31 | 2019 | 9 | Classifying k-edge colouring for H-free graphs | E Galby, PT Lima, D Paulusma, B Ries - Information Processing Letters, 2019 - Elsevier | ||
| 32 | 2018 | 7 | On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size | DV Sirotkin, DS Malyshev - Journal of Applied and Industrial Mathematics, 2018 - Springer | ||
| 33 | 2022 | 2 | List locally surjective homomorphisms in hereditary graph classes | P Dvořák, M Krawczyk, T Masařík, J Novotná… - arXiv preprint arXiv …, 2022 - arxiv.org | ||
| 34 | 2020 | 9 | Obstructions for Three-Coloring and List Three-Coloring -Free Graphs | M Chudnovsky, J Goedgebeur, O Schaudt… - SIAM Journal on Discrete …, 2020 - SIAM | ||
| 35 | 2008 | 5 | -Colouring -free graphs without short odd cycles | A Rojas, M Stein - arXiv preprint arXiv:2008.04845, 2020 - arxiv.org | ||
| 36 | 2206 | 1 | List-3-Coloring ordered graphs with a forbidden induced subgraph | S Hajebi, Y Li, S Spirkl - arXiv preprint arXiv:2206.06543, 2022 - arxiv.org | ||
| 37 | 2023 | 0 | A Complete Complexity Dichotomy of the Edge-Coloring Problem for All Sets of-Edge Forbidden Subgraphs | DS Malyshev, OI Duginov - Journal of Applied and Industrial Mathematics, 2023 - Springer | ||
| 38 | 2305 | 0 | List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs | BB Şen, ÖY Diner, T Erlebach - arXiv preprint arXiv:2305.10108, 2023 - arxiv.org | ||
| 39 | 2021 | 8 | Better 3-coloring algorithms: excluding a triangle and a seven vertex path | F Bonomo-Braberman, M Chudnovsky… - Theoretical Computer …, 2021 - Elsevier | ||
| 40 | 2020 | 4 | Covering minimal separators and potential maximal cliques in -free graphs | A Grzesik, T Klimošová, M Pilipczuk… - arXiv preprint arXiv …, 2020 - arxiv.org | ||
| 41 | 2022 | 1 | An intractability result for the vertex 3-colourability problem | DS Malyshev, OV Pristavchenko - Optimization Letters, 2022 - Springer | ||
| 42 | 2018 | 6 | List-three-coloring graphs with no induced | M Chudnovsky, S Huang, S Spirkl, M Zhong - arXiv preprint arXiv …, 2018 - arxiv.org | ||
| 43 | 2023 | 0 | List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs | B Baklan Şen, Ö Yaşar Diner, T Erlebach - International Computing and …, 2023 - Springer | ||
| 44 | 2022 | 0 | On 3-Coloring of ([... formula...])-Free Graphs | V Jelínek, T Klimošová, T Masařík, J Novotná… - Algorithmica, 2022 - ncbi.nlm.nih.gov | ||
| 45 | 2020 | 2 | Complete Complexity Dichotomy for-Edge Forbidden Subgraphs in the Edge Coloring Problem | DS Malyshev - Journal of Applied and Industrial Mathematics, 2020 - Springer | ||
| 46 | 2019 | 6 | Hereditary graph classes: When the complexities of coloring and clique cover coincide | A Blanché, KK Dabrowski, M Johnson… - Journal of Graph …, 2019 - Wiley Online Library | ||
| 47 | 2023 | 0 | 3-Colouring -Free Graphs Without Short Odd Cycles | A Rojas Anríquez, M Stein - Algorithmica, 2023 - Springer | ||
| 48 | 2021 | 3 | Structural domination and coloring of some (P7, C7)-free graphs | SA Choudum, T Karthick, MM Belavadi - Discrete Mathematics, 2021 - Elsevier | ||
| 49 | 2020 | 3 | Constructing balanced, conflict-minimal, overlap-fair channel sensing schedules | P Aragao, R Gotzhein - … Networking and Applications: Proceedings of the …, 2020 - Springer | ||
| 50 | 2023 | 1 | 3-Coloring or -Free Diameter Two Graphs | T Klimošová, V Sahlot - Algorithms and Data Structures Symposium, 2023 - Springer | ||
| 51 | 2021 | 1 | The vertex colourability problem for {claw, butterfly\} claw, butterfly-free graphs is polynomial-time solvable | DS Malyshev - Optimization Letters, 2021 - Springer | ||
| 52 | 2023 | 0 | Inapproximability of Maximum Diameter Clustering for Few Clusters | H Fleischmann, K Karlov, A Padaki… - arXiv preprint arXiv …, 2023 - arxiv.org | ||
| 53 | 2020 | 4 | Connected greedy coloring of H-free graphs | E Mota, L Rocha, A Silva - Discrete Applied Mathematics, 2020 - Elsevier | ||
| 54 | 2019 | 3 | Approximately coloring graphs without long induced paths | M Chudnovsky, O Schaudt, S Spirkl, M Stein, M Zhong - Algorithmica, 2019 - Springer | ||
| 55 | 2022 | 2 | On 3-Coloring of ()-Free Graphs | V Jelínek, T Klimošová, T Masařík, J Novotná… - Algorithmica, 2022 - Springer | ||
| 56 | 2020 | 2 | List k-colouring Pt-free graphs with no induced 1-subdivision of K1, s: a mim-width perspective | N Brettell, A Munaro, D Paulusma - arXiv preprint arXiv …, 2020 - researchgate.net | ||
| 57 | 2022 | 0 | Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter | B Martin, D Paulusma, S Smith - Theoretical Computer Science, 2022 - Elsevier | ||
| 58 | 2022 | 0 | On coloring a class of claw-free and hole-twin-free graphs | Y Dai, AM Foley, CT Hoàng - Discrete Applied Mathematics, 2022 - Elsevier | ||
| 59 | 2022 | 0 | Time-Slotted Schedule-based Channel Sensing in 802.11 Ad-hoc Networks | K Schneider - 2022 - kluedo.ub.rptu.de | ||
| 60 | 2022 | 0 | Graph Partitioning With Input Restrictions | S Smith - 2022 - etheses.dur.ac.uk | ||
| 61 | 2024 | 2 | Four-Coloring -Free Graphs. II. Finding an Excellent Precoloring | M Chudnovsky, S Spirkl, M Zhong - SIAM Journal on Computing, 2024 - SIAM | ||
| 62 | 2024 | 2 | Four-Coloring -Free Graphs. I. Extending an Excellent Precoloring | M Chudnovsky, S Spirkl, M Zhong - SIAM Journal on Computing, 2024 - SIAM | ||
| 63 | 2022 | 0 | Coloring Algorithms for Graphs and Hypergraphs with Forbidden Substructures | Y Li - 2022 - uwspace.uwaterloo.ca | ||
| 64 | 2020 | 0 | A perspective on theoretical computer science in Latin America | M Kiwi, Y Kohayakawa, S Rajsbaum… - Communications of the …, 2020 - dl.acm.org | ||
| 65 | 2021 | 0 | Graph problems motivated by (low and high) resolution models of large protein assemblies | VH Nguyen - 2021 - inria.hal.science | ||
| 66 | 2020 | 1 | Structure for algorithms, graph reconstruction and hypercube intersections | C Groenland - 2020 - ora.ox.ac.uk | ||
| 67 | 2019 | 1 | Coloring of pseudocubic graphs in three colors | SN Selezneva, MV Mel'nik, AV Astakhova - … Mathematics and Cybernetics, 2019 - Springer | ||
| 68 | 2018 | 3 | О сложности задачи вершинной -раскраски для наследственных классов графов, определённых запретами небольшого размера | ДВ Сироткин, ДС Малышев - Дискретный анализ и исследование …, 2018 - mathnet.ru | ||
| 69 | 2020 | 0 | A note on 3-coloring of (2P4, C5)-free graphs | V Jelínek, T Klimošová, T Masařík… - arXiv preprint arXiv …, 2020 - researchgate.net | ||
| 70 | 2021 | 0 | Complexity of -coloring -free Graphs | F Jacques, P Ochem - … Conference on Combinatorics, Graph Theory and …, 2021 - Springer | ||
| 71 | 2016 | 1 | Colouring on hereditary graph classes closed under complementation | A Blanché, KK Dabrowski, M Johnson… - arXiv preprint arXiv …, 2016 - researchgate.net | ||
| 72 | 2020 | 0 | k-Critical Graphs in-Free Graphs | K Cameron, J Goedgebeur, S Huang, Y Shi - International Computing and …, 2020 - Springer | ||
| 73 | 2020 | 0 | Price of connectivity of graph parameters | T Hulcová - 2020 - dspace.cuni.cz | ||
| 74 | 2020 | 0 | Vertex Coloring of a Graph for Memory Constrained Scenarios | ESA da Silva, H Pedrini - Mathematics in Computer Science, 2020 - Springer | ||
| 75 | 2022 | 0 | Time-Slotted Schedule-based Channel Sensing in 802.11 Ad-hoc Networks | PF Aragao Alves Junior - 2022 - kluedo.ub.rptu.de | ||
| 76 | 2020 | 0 | A perspective on theoretical computer science in Latin America | M Kiwi Krauskopf, Y Kohayakawa, S Rajsbaum… - 2020 - repositorio.uchile.cl | ||
| 77 | 2021 | 0 | Problèmes de graphes motivés par des modèles basse et haute résolution de grands assemblages de protéines | TVH Nguyen - 2021 - theses.fr | ||
| 78 | 2020 | 1 | Полная сложностная дихотомия для запрещённых подграфов с 7 рёбрами в задаче о хроматическом индексе | ДС Малышев - Дискретный анализ и исследование операций, 2020 - mathnet.ru | ||
| 79 | 2023 | 0 | 3-Colouring Pt-free graphs without short odd cycles | AR Anrıquez, M Stein - 2023 - dim.uchile.cl | ||
| 80 | 0 | Longer cycles in essentially 4-connected planar graphs | S Mohr - Dear Participant - umv.science.upjs.sk | |||
| 81 | 0 | 4 Open problems 4.1 Parameterized complexity of the coloring problems for H-free graphs | PA Golovach - Graph Colouring: from Structure to Algorithms - scholar.archive.org | |||
| 82 | 0 | 1 Imię i nazwisko | P Rzążewski - mimuw.edu.pl | |||
| 83 | 0 | List 3-coloring graphs with no induced P6 | M Chudnovsky, S Huang, S Spirkl, M Zhong - math.princeton.edu | |||
| 84 | 2019 | 1 | Раскраска в три цвета псевдокубических графов | СН Селезнева, МВ Мельник… - … университета. Серия 15 …, 2019 - cyberleninka.ru | ||
| 85 | 2018 | 0 | Dominating sets in graphs with no long induced paths | J Shi - 2018 - mit.edu | ||
| 86 | 2017 | 0 | Coloring, stable set and structure of graphs | L Pastor - 2017 - theses.hal.science | ||
| 87 | 2020 | 1 | Полная классификация сложности задачи о вершинной 3-раскраске для четверок порожденных 5-вершинных запретов | ДС Малышев - Журнал Средневолжского математического …, 2020 - mathnet.ru | ||
| 88 | 0 | ИССЛЕДОВАНИЕ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ЗАДАЧ О НЕЗАВИСИМОМ МНОЖЕСТВЕ И О ВЕРШИННОЙ k-РАСКРАСКЕ В НЕКОТОРЫХ … | ДВ Сироткин - diss.unn.ru | |||
| 89 | 2019 | 0 | 3-coloreo en grafos con caminos y ciclos prohibidos | AB Rojas Anríquez - 2019 - repositorio.uchile.cl | ||
| 90 | 2019 | 0 | ОБ АЛГОРИТМИЧЕСКОЙ СЛОЖНОСТИ ЗАДАЧ О РАСКРАСКЕ В СЕМЕЙСТВЕ НАСЛЕДСТВЕННЫХ КЛАССОВ ГРАФОВ, ОПРЕДЕЛЯЕМЫХ … | ДС Малышев - … семинара Дискретная ма-тематика и ее …, 2019 - keldysh.ru | ||
| 91 | 2019 | 0 | РАСКРАСКИ ПСЕВДОРЕГУЛЯРНЫХ ГРАФОВ | СН Селезнева, МВ Мельник - … ма-тематика и ее приложения, имени …, 2019 - keldysh.ru | ||
| 92 | 2017 | 0 | Coloration, ensemble indépendant et structure de graphe | L Pastor - 2017 - theses.fr | ||
| 93 | 1607 | 1 | A Blanché, KK Dabrowski, M Johnson, D Paulusma - arXiv preprint arXiv:1607.06757, 2016 | |||
| 94 | 0 | M Chudnovsky, J Goedgebeur, O Schaudt, M Zhong | ||||
| 95 | 2018 | 0 | О СЛОЖНОСТИ ЗАДАЧИ О ВЕРШИННОЙ 3-РАСКРАСКЕ ДЛЯ НАСЛЕДСТВЕННЫХ КЛАССОВ С МАЛЫМИ ЗАПРЕТАМИ | ДС Малышев - Дискретные модели в теории управляющих систем, 2018 - elibrary.ru |