The complexity of strong conflict-free vertex-connection $k$-colorability Article Swipe

PDF

Sun‐Yuan Hsieh , Hoàng-Oanh Le , Van Bang Lê , Sheng‐Lung Peng ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2408.05865

We study a new variant of graph coloring by adding a connectivity constraint. A path in a vertex-colored graph is called conflict-free if there is a color that appears exactly once on its vertices. A connected graph $G$ is said to be strongly conflict-free vertex-connection $k$-colorable if $G$ admits a vertex $k$-coloring such that any two distinct vertices of $G$ are connected by a conflict-free $shortest$ path. Among others, we show that deciding whether a given graph is strongly conflict-free vertex-connection $3$-colorable is NP-complete even when restricted to $3$-colorable graphs with diameter $3$, radius $2$ and domination number $3$, and, assuming the Exponential Time Hypothesis (ETH), cannot be solved in $2^{o(n)}$ time on such restricted input graphs with $n$ vertices. This hardness result is quite strong when compared to the ordinary $3$-COLORING problem: it is known that $3$-COLORING is solvable in polynomial time in graphs with bounded domination number, and assuming ETH, cannot be solved in $2^{o(\sqrt{n})}$ time in $n$-vertex graphs with diameter $3$ and radius $2$. On the positive side, we point out that a strong conflict-free vertex-connection coloring with minimum color number of a given split graph or a co-bipartite graph can be computed in polynomial time.

Related Topics

Vertex (Graph Theory)

Concepts

Connection (principal bundle) Vertex (graph theory) Combinatorics Computer science Mathematics Graph Geometry

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2408.05865
PDF: https://arxiv.org/pdf/2408.05865
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4402426730

All OpenAlex metadata

Raw OpenAlex JSON

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

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

Digital Object Identifier
Title: The complexity of strong conflict-free vertex-connection $k$-colorability

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-08-11

Full publication date if available
Authors: Sun‐Yuan Hsieh, Hoàng-Oanh Le, Van Bang Lê, Sheng‐Lung Peng

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

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

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/2408.05865

Direct OA link when available
Concepts: Connection (principal bundle), Vertex (graph theory), Combinatorics, Computer science, Mathematics, Graph, Geometry

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4402426730
doi	https://doi.org/10.48550/arxiv.2408.05865
ids.doi	https://doi.org/10.48550/arxiv.2408.05865
ids.openalex	https://openalex.org/W4402426730
fwci
type	preprint
title	The complexity of strong conflict-free vertex-connection $k$-colorability
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10374
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9649999737739563
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Advanced Graph Theory Research
topics[1].id	https://openalex.org/T12541
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9649999737739563
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1703
topics[1].subfield.display_name	Computational Theory and Mathematics
topics[1].display_name	Graph Labeling and Dimension Problems
topics[2].id	https://openalex.org/T10996
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9154000282287598
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1704
topics[2].subfield.display_name	Computer Graphics and Computer-Aided Design
topics[2].display_name	Computational Geometry and Mesh Generation
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C13355873
concepts[0].level	2
concepts[0].score	0.6103450655937195
concepts[0].wikidata	https://www.wikidata.org/wiki/Q2920850
concepts[0].display_name	Connection (principal bundle)
concepts[1].id	https://openalex.org/C80899671
concepts[1].level	3
concepts[1].score	0.6021643877029419
concepts[1].wikidata	https://www.wikidata.org/wiki/Q1304193
concepts[1].display_name	Vertex (graph theory)
concepts[2].id	https://openalex.org/C114614502
concepts[2].level	1
concepts[2].score	0.4982028007507324
concepts[2].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[2].display_name	Combinatorics
concepts[3].id	https://openalex.org/C41008148
concepts[3].level	0
concepts[3].score	0.40689006447792053
concepts[3].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[3].display_name	Computer science
concepts[4].id	https://openalex.org/C33923547
concepts[4].level	0
concepts[4].score	0.38583606481552124
concepts[4].wikidata	https://www.wikidata.org/wiki/Q395
concepts[4].display_name	Mathematics
concepts[5].id	https://openalex.org/C132525143
concepts[5].level	2
concepts[5].score	0.11464619636535645
concepts[5].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[5].display_name	Graph
concepts[6].id	https://openalex.org/C2524010
concepts[6].level	1
concepts[6].score	0.10466533899307251
concepts[6].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[6].display_name	Geometry
keywords[0].id	https://openalex.org/keywords/connection
keywords[0].score	0.6103450655937195
keywords[0].display_name	Connection (principal bundle)
keywords[1].id	https://openalex.org/keywords/vertex
keywords[1].score	0.6021643877029419
keywords[1].display_name	Vertex (graph theory)
keywords[2].id	https://openalex.org/keywords/combinatorics
keywords[2].score	0.4982028007507324
keywords[2].display_name	Combinatorics
keywords[3].id	https://openalex.org/keywords/computer-science
keywords[3].score	0.40689006447792053
keywords[3].display_name	Computer science
keywords[4].id	https://openalex.org/keywords/mathematics
keywords[4].score	0.38583606481552124
keywords[4].display_name	Mathematics
keywords[5].id	https://openalex.org/keywords/graph
keywords[5].score	0.11464619636535645
keywords[5].display_name	Graph
keywords[6].id	https://openalex.org/keywords/geometry
keywords[6].score	0.10466533899307251
keywords[6].display_name	Geometry
language	en
locations[0].id	pmh:oai:arXiv.org:2408.05865
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/2408.05865
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/2408.05865
locations[1].id	doi:10.48550/arxiv.2408.05865
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.2408.05865
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5103047340
authorships[0].author.orcid	https://orcid.org/0000-0003-4746-3179
authorships[0].author.display_name	Sun‐Yuan Hsieh
authorships[0].author_position	first
authorships[0].raw_author_name	Hsieh, Sun-Yuan
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5007008004
authorships[1].author.orcid
authorships[1].author.display_name	Hoàng-Oanh Le
authorships[1].author_position	middle
authorships[1].raw_author_name	Le, Hoang-Oanh
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5072055012
authorships[2].author.orcid	https://orcid.org/0000-0002-3303-8326
authorships[2].author.display_name	Van Bang Lê
authorships[2].author_position	middle
authorships[2].raw_author_name	Le, Van Bang
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5025918292
authorships[3].author.orcid	https://orcid.org/0000-0002-9484-6677
authorships[3].author.display_name	Sheng‐Lung Peng
authorships[3].author_position	last
authorships[3].raw_author_name	Peng, Sheng-Lung
authorships[3].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/2408.05865
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2024-09-11T00:00:00
display_name	The complexity of strong conflict-free vertex-connection $k$-colorability
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10374
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9649999737739563
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Advanced Graph Theory Research
related_works	https://openalex.org/W2748952813, https://openalex.org/W4391375266, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2142036596, https://openalex.org/W2072657027, https://openalex.org/W3111310291
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2408.05865
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/2408.05865
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/2408.05865
primary_location.id	pmh:oai:arXiv.org:2408.05865
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/2408.05865
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/2408.05865
publication_date	2024-08-11
publication_year	2024
referenced_works_count	0
abstract_inverted_index.A	13, 34
abstract_inverted_index.a	2, 10, 16, 25, 49, 63, 74, 175, 185, 190
abstract_inverted_index.On	167
abstract_inverted_index.We	0
abstract_inverted_index.be	41, 107, 153, 194
abstract_inverted_index.by	8, 62
abstract_inverted_index.if	22, 46
abstract_inverted_index.in	15, 109, 140, 143, 155, 158, 196
abstract_inverted_index.is	19, 24, 38, 77, 82, 123, 134, 138
abstract_inverted_index.it	133
abstract_inverted_index.of	5, 58, 184
abstract_inverted_index.on	31, 112
abstract_inverted_index.or	189
abstract_inverted_index.to	40, 87, 128
abstract_inverted_index.we	69, 171
abstract_inverted_index.$2$	94
abstract_inverted_index.$3$	163
abstract_inverted_index.$G$	37, 47, 59
abstract_inverted_index.$n$	118
abstract_inverted_index.and	95, 149, 164
abstract_inverted_index.any	54
abstract_inverted_index.are	60
abstract_inverted_index.can	193
abstract_inverted_index.its	32
abstract_inverted_index.new	3
abstract_inverted_index.out	173
abstract_inverted_index.the	101, 129, 168
abstract_inverted_index.two	55
abstract_inverted_index.$2$.	166
abstract_inverted_index.$3$,	92, 98
abstract_inverted_index.ETH,	151
abstract_inverted_index.This	120
abstract_inverted_index.Time	103
abstract_inverted_index.and,	99
abstract_inverted_index.even	84
abstract_inverted_index.once	30
abstract_inverted_index.path	14
abstract_inverted_index.said	39
abstract_inverted_index.show	70
abstract_inverted_index.such	52, 113
abstract_inverted_index.that	27, 53, 71, 136, 174
abstract_inverted_index.time	111, 142, 157
abstract_inverted_index.when	85, 126
abstract_inverted_index.with	90, 117, 145, 161, 180
abstract_inverted_index.Among	67
abstract_inverted_index.color	26, 182
abstract_inverted_index.given	75, 186
abstract_inverted_index.graph	6, 18, 36, 76, 188, 192
abstract_inverted_index.input	115
abstract_inverted_index.known	135
abstract_inverted_index.path.	66
abstract_inverted_index.point	172
abstract_inverted_index.quite	124
abstract_inverted_index.side,	170
abstract_inverted_index.split	187
abstract_inverted_index.study	1
abstract_inverted_index.there	23
abstract_inverted_index.time.	198
abstract_inverted_index.(ETH),	105
abstract_inverted_index.adding	9
abstract_inverted_index.admits	48
abstract_inverted_index.called	20
abstract_inverted_index.cannot	106, 152
abstract_inverted_index.graphs	89, 116, 144, 160
abstract_inverted_index.number	97, 183
abstract_inverted_index.radius	93, 165
abstract_inverted_index.result	122
abstract_inverted_index.solved	108, 154
abstract_inverted_index.strong	125, 176
abstract_inverted_index.vertex	50
abstract_inverted_index.appears	28
abstract_inverted_index.bounded	146
abstract_inverted_index.exactly	29
abstract_inverted_index.minimum	181
abstract_inverted_index.number,	148
abstract_inverted_index.others,	68
abstract_inverted_index.variant	4
abstract_inverted_index.whether	73
abstract_inverted_index.assuming	100, 150
abstract_inverted_index.coloring	7, 179
abstract_inverted_index.compared	127
abstract_inverted_index.computed	195
abstract_inverted_index.deciding	72
abstract_inverted_index.diameter	91, 162
abstract_inverted_index.distinct	56
abstract_inverted_index.hardness	121
abstract_inverted_index.ordinary	130
abstract_inverted_index.positive	169
abstract_inverted_index.problem:	132
abstract_inverted_index.solvable	139
abstract_inverted_index.strongly	42, 78
abstract_inverted_index.vertices	57
abstract_inverted_index.connected	35, 61
abstract_inverted_index.vertices.	33, 119
abstract_inverted_index.$2^{o(n)}$	110
abstract_inverted_index.$n$-vertex	159
abstract_inverted_index.$shortest$	65
abstract_inverted_index.Hypothesis	104
abstract_inverted_index.domination	96, 147
abstract_inverted_index.polynomial	141, 197
abstract_inverted_index.restricted	86, 114
abstract_inverted_index.Exponential	102
abstract_inverted_index.NP-complete	83
abstract_inverted_index.constraint.	12
abstract_inverted_index.$3$-COLORING	131, 137
abstract_inverted_index.$k$-coloring	51
abstract_inverted_index.co-bipartite	191
abstract_inverted_index.connectivity	11
abstract_inverted_index.$3$-colorable	81, 88
abstract_inverted_index.$k$-colorable	45
abstract_inverted_index.conflict-free	21, 43, 64, 79, 177
abstract_inverted_index.vertex-colored	17
abstract_inverted_index.$2^{o(\sqrt{n})}$	156
abstract_inverted_index.vertex-connection	44, 80, 178
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile