Regular pattern-free coloring

Simple item page
dc.contributor.authorEscamocher, Guillaume
dc.contributor.authorO'Sullivan, Barry
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderEuropean Regional Development Funden
dc.date.accessioned2022-07-05T11:06:16Z
dc.date.available2022-07-05T11:06:16Z
dc.date.issued2022-11-15
dc.date.updated2022-07-05T11:01:24Z
dc.description.abstractWe 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.en
dc.description.sponsorshipScience Foundation Ireland (Grant No. 12/RC/2289-P2 which is co-funded under the European Regional Development Fund)en
dc.description.statusPeer revieweden
dc.description.versionPublished Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationEscamocher, 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.034en
dc.identifier.doi10.1016/j.dam.2022.06.034en
dc.identifier.endpage125en
dc.identifier.issn0166-218X
dc.identifier.journaltitleDiscrete Applied Mathematicsen
dc.identifier.startpage109en
dc.identifier.urihttps://hdl.handle.net/10468/13338
dc.identifier.volume321en
dc.language.isoenen
dc.publisherElsevieren
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.relation.urihttps://www.sciencedirect.com/science/article/pii/S0166218X2200227X
dc.rights© 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).en
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.subjectGraph coloringen
dc.subjectForbidden subgraphsen
dc.subjectRegular graphsen
dc.subjectComplexity resultsen
dc.subjectDifficult instance generationen
dc.titleRegular pattern-free coloringen
dc.typeArticle (peer-reviewed)en
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
1-s2.0-S0166218X2200227X-main.pdf
Size:
1.54 MB
Format:
Adobe Portable Document Format
Description:
Published version
Download
Thumbnail Image
Name:
1-s2.0-S0166218X2200227X-mmc1.zip
Size:
6.23 KB
Format:
http://www.iana.org/assignments/media-types/application/zip
Description:
Supplementary data
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Journal Articles
Insight Centre for Data Analytics - Journal Articles