Regular pattern-free coloring
Loading...
Files
Published version
Supplementary data
Date
2022-11-15
Authors
Escamocher, Guillaume
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Published Version
Abstract
We study the graph coloring problem under two kinds of simultaneous restrictions. First we forbid some patterns to appear in the graph, where a pattern is a small subgraph. Second we only consider regular graphs, meaning that all nodes have the same degree. Having both types of constraints at once leads us to the discovery of new tractable classes for graph coloring. However, we also show that some classes of pattern-free graphs remain NP-Complete even after enforcing regularity. Based on the latter results, we provide several complementary ways to generate difficult graph coloring instances, relying on balancing the degree of the nodes and avoiding a particular subgraph. Our constructions are parameterizable, so characteristics of the instances like size (number of nodes) and density (number of edges) can be set to any value.
Description
Keywords
Graph coloring , Forbidden subgraphs , Regular graphs , Complexity results , Difficult instance generation
Citation
Escamocher, G. and O'Sullivan, B. (2022) 'Regular pattern-free coloring', Discrete Applied Mathematics, 321, pp. 109-125. https://doi.org/10.1016/j.dam.2022.06.034