On 3-coloring of \((2P_4,C_5)\)-free graphs
From MaRDI portal
Publication:5925555
DOI10.1007/978-3-030-86838-3_30OpenAlexW3202824928MaRDI QIDQ5925555
Jana Novotná, Tomáš Masařík, Aneta Pokorná, Tereza Klimošová, Vít Jelínek
Publication date: 8 June 2022
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2011.06173
Related Items
Uses Software
Cites Work
- Unnamed Item
- Complexity of coloring graphs without paths and cycles
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- The strong perfect graph theorem
- Clustering and domination in perfect graphs
- Some perfect coloring properties of graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Colouring \((P_r + P_s)\)-free graphs
- List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
- Better 3-coloring algorithms: excluding a triangle and a seven vertex path
- List 3-coloring graphs with no induced \(P_6 + rP_3\)
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- List coloring in the absence of a linear forest
- Coloring graphs without short cycles and long induced paths
- 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- The NP-Completeness of Edge-Coloring
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Exhaustive generation of k‐critical ‐free graphs
- 3-Colorable Subclasses of $P_8$-Free Graphs
- NP completeness of finding the chromatic index of regular graphs
- Reducibility among Combinatorial Problems
- Four-coloring P6-free graphs
- Narrowing the Complexity Gap for Colouring (C s ,P t )-Free Graphs
- The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
