HyColor: An Efficient Heuristic Algorithm for Graph Coloring Article Swipe

PDF

Enqiang Zhu , Yu Zhang , Haopeng Sun , Wei Zhang , Witold Pedrycz , Chanjuan Liu , Jin Xu ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2506.07373

The graph coloring problem (GCP) is a classic combinatorial optimization problem that aims to find the minimum number of colors assigned to vertices of a graph such that no two adjacent vertices receive the same color. GCP has been extensively studied by researchers from various fields, including mathematics, computer science, and biological science. Due to the NP-hard nature, many heuristic algorithms have been proposed to solve GCP. However, existing GCP algorithms focus on either small hard graphs or large-scale sparse graphs (with up to 10^7 vertices). This paper presents an efficient hybrid heuristic algorithm for GCP, named HyColor, which excels in handling large-scale sparse graphs while achieving impressive results on small dense graphs. The efficiency of HyColor comes from the following three aspects: a local decision strategy to improve the lower bound on the chromatic number; a graph-reduction strategy to reduce the working graph; and a k-core and mixed degree-based greedy heuristic for efficiently coloring graphs. HyColor is evaluated against three state-of-the-art GCP algorithms across four benchmarks, comprising three large-scale sparse graph benchmarks and one small dense graph benchmark, totaling 209 instances. The results demonstrate that HyColor consistently outperforms existing heuristic algorithms in both solution accuracy and computational efficiency for the majority of instances. Notably, HyColor achieved the best solutions in 194 instances (over 93%), with 34 of these solutions significantly surpassing those of other algorithms. Furthermore, HyColor successfully determined the chromatic number and achieved optimal coloring in 128 instances.

Related Topics

Truth And Reconciliation Commission Of Canada

Concepts

No concepts available.

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2506.07373
PDF: https://arxiv.org/pdf/2506.07373
OA Status: green
OpenAlex ID: https://openalex.org/W4417097932

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4417097932

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2506.07373

Digital Object Identifier
Title: HyColor: An Efficient Heuristic Algorithm for Graph Coloring

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-06-09

Full publication date if available
Authors: Enqiang Zhu, Yu Zhang, Haopeng Sun, Wei Zhang, Witold Pedrycz, Chanjuan Liu, Jin Xu

List of authors in order
Landing page: https://arxiv.org/abs/2506.07373

Publisher landing page
PDF URL: https://arxiv.org/pdf/2506.07373

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2506.07373

Direct OA link when available
Cited by: 0

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W4417097932
doi	https://doi.org/10.48550/arxiv.2506.07373
ids.doi	https://doi.org/10.48550/arxiv.2506.07373
ids.openalex	https://openalex.org/W4417097932
fwci
type	preprint
title	HyColor: An Efficient Heuristic Algorithm for Graph Coloring
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
is_xpac	False
apc_list
apc_paid
language	en
locations[0].id	pmh:oai:arXiv.org:2506.07373
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2506.07373
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2506.07373
locations[1].id	doi:10.48550/arxiv.2506.07373
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2506.07373
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5004232829
authorships[0].author.orcid	https://orcid.org/0000-0002-5245-7905
authorships[0].author.display_name	Enqiang Zhu
authorships[0].author_position	first
authorships[0].raw_author_name	Zhu, Enqiang
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5100617203
authorships[1].author.orcid	https://orcid.org/0000-0003-0060-4544
authorships[1].author.display_name	Yu Zhang
authorships[1].author_position	middle
authorships[1].raw_author_name	Zhang, Yu
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5031755924
authorships[2].author.orcid	https://orcid.org/0000-0002-5109-0304
authorships[2].author.display_name	Haopeng Sun
authorships[2].author_position	middle
authorships[2].raw_author_name	Sun, Haopeng
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5000814233
authorships[3].author.orcid	https://orcid.org/0000-0002-0195-2666
authorships[3].author.display_name	Wei Zhang
authorships[3].author_position	middle
authorships[3].raw_author_name	Wei, Ziqi
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5003799782
authorships[4].author.orcid	https://orcid.org/0000-0002-9335-9930
authorships[4].author.display_name	Witold Pedrycz
authorships[4].author_position	middle
authorships[4].raw_author_name	Pedrycz, Witold
authorships[4].is_corresponding	False
authorships[5].author.id	https://openalex.org/A5053853994
authorships[5].author.orcid	https://orcid.org/0009-0002-0342-5891
authorships[5].author.display_name	Chanjuan Liu
authorships[5].author_position	middle
authorships[5].raw_author_name	Liu, Chanjuan
authorships[5].is_corresponding	False
authorships[6].author.id	https://openalex.org/A5101605362
authorships[6].author.orcid	https://orcid.org/0000-0002-6021-5551
authorships[6].author.display_name	Jin Xu
authorships[6].author_position	last
authorships[6].raw_author_name	Xu, Jin
authorships[6].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2506.07373
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	HyColor: An Efficient Heuristic Algorithm for Graph Coloring
has_fulltext	False
is_retracted	False
updated_date	2025-12-10T02:45:41.426853
primary_topic
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2506.07373
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2506.07373
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2506.07373
primary_location.id	pmh:oai:arXiv.org:2506.07373
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2506.07373
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2506.07373
publication_date	2025-06-09
publication_year	2025
referenced_works_count	0
abstract_inverted_index.a	6, 24, 123, 136, 145
abstract_inverted_index.34	216
abstract_inverted_index.an	89
abstract_inverted_index.by	41
abstract_inverted_index.in	100, 192, 210, 237
abstract_inverted_index.is	5, 157
abstract_inverted_index.no	28
abstract_inverted_index.of	18, 23, 115, 202, 217, 223
abstract_inverted_index.on	72, 109, 132
abstract_inverted_index.or	77
abstract_inverted_index.to	13, 21, 54, 64, 83, 127, 139
abstract_inverted_index.up	82
abstract_inverted_index.128	238
abstract_inverted_index.194	211
abstract_inverted_index.209	180
abstract_inverted_index.Due	53
abstract_inverted_index.GCP	36, 69, 162
abstract_inverted_index.The	0, 113, 182
abstract_inverted_index.and	50, 144, 147, 173, 196, 233
abstract_inverted_index.for	94, 152, 199
abstract_inverted_index.has	37
abstract_inverted_index.one	174
abstract_inverted_index.the	15, 33, 55, 119, 129, 133, 141, 200, 207, 230
abstract_inverted_index.two	29
abstract_inverted_index.10^7	84
abstract_inverted_index.GCP,	95
abstract_inverted_index.GCP.	66
abstract_inverted_index.This	86
abstract_inverted_index.aims	12
abstract_inverted_index.been	38, 62
abstract_inverted_index.best	208
abstract_inverted_index.both	193
abstract_inverted_index.find	14
abstract_inverted_index.four	165
abstract_inverted_index.from	43, 118
abstract_inverted_index.hard	75
abstract_inverted_index.have	61
abstract_inverted_index.many	58
abstract_inverted_index.same	34
abstract_inverted_index.such	26
abstract_inverted_index.that	11, 27, 185
abstract_inverted_index.with	215
abstract_inverted_index.(GCP)	4
abstract_inverted_index.(over	213
abstract_inverted_index.(with	81
abstract_inverted_index.93%),	214
abstract_inverted_index.bound	131
abstract_inverted_index.comes	117
abstract_inverted_index.dense	111, 176
abstract_inverted_index.focus	71
abstract_inverted_index.graph	1, 25, 171, 177
abstract_inverted_index.local	124
abstract_inverted_index.lower	130
abstract_inverted_index.mixed	148
abstract_inverted_index.named	96
abstract_inverted_index.other	224
abstract_inverted_index.paper	87
abstract_inverted_index.small	74, 110, 175
abstract_inverted_index.solve	65
abstract_inverted_index.these	218
abstract_inverted_index.those	222
abstract_inverted_index.three	121, 160, 168
abstract_inverted_index.which	98
abstract_inverted_index.while	105
abstract_inverted_index.across	164
abstract_inverted_index.color.	35
abstract_inverted_index.colors	19
abstract_inverted_index.either	73
abstract_inverted_index.excels	99
abstract_inverted_index.graph;	143
abstract_inverted_index.graphs	76, 80, 104
abstract_inverted_index.greedy	150
abstract_inverted_index.hybrid	91
abstract_inverted_index.k-core	146
abstract_inverted_index.number	17, 232
abstract_inverted_index.reduce	140
abstract_inverted_index.sparse	79, 103, 170
abstract_inverted_index.HyColor	116, 156, 186, 205, 227
abstract_inverted_index.NP-hard	56
abstract_inverted_index.against	159
abstract_inverted_index.classic	7
abstract_inverted_index.fields,	45
abstract_inverted_index.graphs.	112, 155
abstract_inverted_index.improve	128
abstract_inverted_index.minimum	16
abstract_inverted_index.nature,	57
abstract_inverted_index.number;	135
abstract_inverted_index.optimal	235
abstract_inverted_index.problem	3, 10
abstract_inverted_index.receive	32
abstract_inverted_index.results	108, 183
abstract_inverted_index.studied	40
abstract_inverted_index.various	44
abstract_inverted_index.working	142
abstract_inverted_index.However,	67
abstract_inverted_index.HyColor,	97
abstract_inverted_index.Notably,	204
abstract_inverted_index.accuracy	195
abstract_inverted_index.achieved	206, 234
abstract_inverted_index.adjacent	30
abstract_inverted_index.aspects:	122
abstract_inverted_index.assigned	20
abstract_inverted_index.coloring	2, 154, 236
abstract_inverted_index.computer	48
abstract_inverted_index.decision	125
abstract_inverted_index.existing	68, 189
abstract_inverted_index.handling	101
abstract_inverted_index.majority	201
abstract_inverted_index.presents	88
abstract_inverted_index.proposed	63
abstract_inverted_index.science,	49
abstract_inverted_index.science.	52
abstract_inverted_index.solution	194
abstract_inverted_index.strategy	126, 138
abstract_inverted_index.totaling	179
abstract_inverted_index.vertices	22, 31
abstract_inverted_index.achieving	106
abstract_inverted_index.algorithm	93
abstract_inverted_index.chromatic	134, 231
abstract_inverted_index.efficient	90
abstract_inverted_index.evaluated	158
abstract_inverted_index.following	120
abstract_inverted_index.heuristic	59, 92, 151, 190
abstract_inverted_index.including	46
abstract_inverted_index.instances	212
abstract_inverted_index.solutions	209, 219
abstract_inverted_index.algorithms	60, 70, 163, 191
abstract_inverted_index.benchmark,	178
abstract_inverted_index.benchmarks	172
abstract_inverted_index.biological	51
abstract_inverted_index.comprising	167
abstract_inverted_index.determined	229
abstract_inverted_index.efficiency	114, 198
abstract_inverted_index.impressive	107
abstract_inverted_index.instances.	181, 203, 239
abstract_inverted_index.surpassing	221
abstract_inverted_index.vertices).	85
abstract_inverted_index.algorithms.	225
abstract_inverted_index.benchmarks,	166
abstract_inverted_index.demonstrate	184
abstract_inverted_index.efficiently	153
abstract_inverted_index.extensively	39
abstract_inverted_index.large-scale	78, 102, 169
abstract_inverted_index.outperforms	188
abstract_inverted_index.researchers	42
abstract_inverted_index.Furthermore,	226
abstract_inverted_index.consistently	187
abstract_inverted_index.degree-based	149
abstract_inverted_index.mathematics,	47
abstract_inverted_index.optimization	9
abstract_inverted_index.successfully	228
abstract_inverted_index.combinatorial	8
abstract_inverted_index.computational	197
abstract_inverted_index.significantly	220
abstract_inverted_index.graph-reduction	137
abstract_inverted_index.state-of-the-art	161
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	7
citation_normalized_percentile