Regular pattern-free coloring

DOI10.1016/j.dam.2022.06.034zbMath1497.05081OpenAlexW4283775361MaRDI QIDQ2172395

Barry O'Sullivan, Guillaume Escamocher

Publication date: 15 September 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2022.06.034

zbMATH Keywords

graph coloringregular graphsforbidden subgraphscomplexity resultsdifficult instance generation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Uses Software

• CsegGraph
• CPLEX
• GLPK
• MiniZinc

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact algorithm with learning for the graph coloring problem
• Coloring graphs characterized by a forbidden subgraph
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• On singleton arc consistency for CSPs defined by monotone patterns
• Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
• View-based propagator derivation
• Constructive generation of very hard 3-colorability instances
• Graph coloring in the estimation of sparse derivative matrices: Instances and applications
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• The NP-Completeness of Edge-Coloring
• NP completeness of finding the chromatic index of regular graphs
• Frequency planning and ramifications of coloring
• Reducibility among Combinatorial Problems
• Frozen development in graph coloring
• Generating Difficult CNF Instances in Unexplored Constrainedness Regions

This page was built for publication: Regular pattern-free coloring