On 3-coloring of \((2P_4,C_5)\)-free graphs

DOI10.1007/s00453-022-00937-9OpenAlexW4213387244MaRDI QIDQ5918691

Vít Jelínek, Jana Novotná, Aneta Pokorná, Tereza Klimošová, Tomáš Masařík

Publication date: 1 June 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-00937-9

zbMATH Keywords

cographs3-coloringhereditary classes\(2P_4\)-free graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Structural characterization of families of graphs (05C75) Graph theory (05Cxx)

Uses Software

• CriticalPfreeGraphs

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 ₆ ‐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 P₆-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
• On 3-coloring of \((2P_4,C_5)\)-free graphs

This page was built for publication: On 3-coloring of \((2P_4,C_5)\)-free graphs