Chromatic Feature Vectors for 2-Trees: Exact Formulas for Partition Enumeration with Network Applications Article Swipe

PDF

Allagan, J. , Morgan, G. , Langley, S. , Lopez-Bonilla, R. , Deriglazov, V. ·

YOU? · · 2025 · Open Access ·

We establish closed-form enumeration formulas for chromatic feature vectors of 2-trees under the bichromatic triangle constraint. These efficiently computable structural features derive from constrained graph colorings where each triangle uses exactly two colors, forbidding monochromatic and rainbow triangles, a constraint arising in distributed systems where components avoid complete concentration or isolation. For theta graphs Theta_n, we prove r_k(Theta_n) = S(n-2, k-1) for k >= 3 (Stirling numbers of the second kind) and r_2(Theta_n) = 2^(n-2) + 1, computable in O(n) time. For fan graphs Phi_n, we establish r_2(Phi_n) = F_{n+1} (Fibonacci numbers) and derive explicit formulas r_k(Phi_n) = sum_{t=k-1}^{n-1} a_{n-1,t} * S(t, k-1) with efficiently computable binomial coefficients, achieving O(n^2) computation per component. Unlike classical chromatic polynomials, which assign identical features to all n-vertex 2-trees, bichromatic constraints provide informative structural features. While not complete graph invariants, these features capture meaningful structural properties through connections to Fibonacci polynomials, Bell numbers, and independent set enumeration. Applications include Byzantine fault tolerance in hierarchical networks, VM allocation in cloud computing, and secret-sharing protocols in distributed cryptography.

Related Topics

Mathematics

Physarum Polycephalum

Discrete Mathematics

Combinatorics

Vertex (Graph Theory)

Graph Coloring

Computer Science

Theoretical Computer Science

Fibonacci Sequence

Complete Graph

Algorithm

Concepts

Enumeration Chromatic scale Partition (number theory) Mathematics Physarum polycephalum Discrete mathematics Combinatorics Computation Vertex (graph theory) Feature (linguistics) Graph Graph coloring Computer science Graph theory Theoretical computer science Fibonacci number Set (abstract data type) Complete graph Constraint (computer-aided design) Algorithm Constraint satisfaction problem Binomial (polynomial)

Metadata

Type: article
Landing Page: http://arxiv.org/abs/2512.07120
PDF: https://arxiv.org/pdf/2512.07120
OA Status: green
OpenAlex ID: https://openalex.org/W7113916488

All OpenAlex metadata

Raw OpenAlex JSON

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

Canonical identifier for this work in OpenAlex
Title: Chromatic Feature Vectors for 2-Trees: Exact Formulas for Partition Enumeration with Network Applications

Work title
Type: article

OpenAlex work type
Publication year: 2025

Year of publication
Publication date: 2025-12-08

Full publication date if available
Authors: Allagan, J., Morgan, G., Langley, S., Lopez-Bonilla, R., Deriglazov, V.

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

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

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

Direct OA link when available
Concepts: Enumeration, Chromatic scale, Partition (number theory), Mathematics, Physarum polycephalum, Discrete mathematics, Combinatorics, Computation, Vertex (graph theory), Feature (linguistics), Graph, Graph coloring, Computer science, Graph theory, Theoretical computer science, Fibonacci number, Set (abstract data type), Complete graph, Constraint (computer-aided design), Algorithm, Constraint satisfaction problem, Binomial (polynomial)

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

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W7113916488
doi
ids.openalex	https://openalex.org/W7113916488
fwci	0.0
type	article
title	Chromatic Feature Vectors for 2-Trees: Exact Formulas for Partition Enumeration with Network Applications
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10948
topics[0].field.id	https://openalex.org/fields/26
topics[0].field.display_name	Mathematics
topics[0].score	0.2047221064567566
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/2607
topics[0].subfield.display_name	Discrete Mathematics and Combinatorics
topics[0].display_name	Advanced Combinatorial Mathematics
topics[1].id	https://openalex.org/T10237
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.17089779675006866
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1702
topics[1].subfield.display_name	Artificial Intelligence
topics[1].display_name	Cryptography and Data Security
topics[2].id	https://openalex.org/T10374
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.14221030473709106
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1703
topics[2].subfield.display_name	Computational Theory and Mathematics
topics[2].display_name	Advanced Graph Theory Research
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C156340839
concepts[0].level	2
concepts[0].score	0.830542802810669
concepts[0].wikidata	https://www.wikidata.org/wiki/Q2704791
concepts[0].display_name	Enumeration
concepts[1].id	https://openalex.org/C196956537
concepts[1].level	2
concepts[1].score	0.5366489291191101
concepts[1].wikidata	https://www.wikidata.org/wiki/Q202021
concepts[1].display_name	Chromatic scale
concepts[2].id	https://openalex.org/C42812
concepts[2].level	2
concepts[2].score	0.5346030592918396
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1082910
concepts[2].display_name	Partition (number theory)
concepts[3].id	https://openalex.org/C33923547
concepts[3].level	0
concepts[3].score	0.5332451462745667
concepts[3].wikidata	https://www.wikidata.org/wiki/Q395
concepts[3].display_name	Mathematics
concepts[4].id	https://openalex.org/C2780855919
concepts[4].level	2
concepts[4].score	0.5010971426963806
concepts[4].wikidata	https://www.wikidata.org/wiki/Q134950
concepts[4].display_name	Physarum polycephalum
concepts[5].id	https://openalex.org/C118615104
concepts[5].level	1
concepts[5].score	0.4943462014198303
concepts[5].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[5].display_name	Discrete mathematics
concepts[6].id	https://openalex.org/C114614502
concepts[6].level	1
concepts[6].score	0.48989614844322205
concepts[6].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[6].display_name	Combinatorics
concepts[7].id	https://openalex.org/C45374587
concepts[7].level	2
concepts[7].score	0.43807253241539
concepts[7].wikidata	https://www.wikidata.org/wiki/Q12525525
concepts[7].display_name	Computation
concepts[8].id	https://openalex.org/C80899671
concepts[8].level	3
concepts[8].score	0.41906607151031494
concepts[8].wikidata	https://www.wikidata.org/wiki/Q1304193
concepts[8].display_name	Vertex (graph theory)
concepts[9].id	https://openalex.org/C2776401178
concepts[9].level	2
concepts[9].score	0.4111732542514801
concepts[9].wikidata	https://www.wikidata.org/wiki/Q12050496
concepts[9].display_name	Feature (linguistics)
concepts[10].id	https://openalex.org/C132525143
concepts[10].level	2
concepts[10].score	0.40103650093078613
concepts[10].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[10].display_name	Graph
concepts[11].id	https://openalex.org/C76946457
concepts[11].level	3
concepts[11].score	0.3807755410671234
concepts[11].wikidata	https://www.wikidata.org/wiki/Q504843
concepts[11].display_name	Graph coloring
concepts[12].id	https://openalex.org/C41008148
concepts[12].level	0
concepts[12].score	0.37306922674179077
concepts[12].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[12].display_name	Computer science
concepts[13].id	https://openalex.org/C88230418
concepts[13].level	2
concepts[13].score	0.3307209014892578
concepts[13].wikidata	https://www.wikidata.org/wiki/Q131476
concepts[13].display_name	Graph theory
concepts[14].id	https://openalex.org/C80444323
concepts[14].level	1
concepts[14].score	0.32953330874443054
concepts[14].wikidata	https://www.wikidata.org/wiki/Q2878974
concepts[14].display_name	Theoretical computer science
concepts[15].id	https://openalex.org/C173734053
concepts[15].level	2
concepts[15].score	0.3264259099960327
concepts[15].wikidata	https://www.wikidata.org/wiki/Q47577
concepts[15].display_name	Fibonacci number
concepts[16].id	https://openalex.org/C177264268
concepts[16].level	2
concepts[16].score	0.319364070892334
concepts[16].wikidata	https://www.wikidata.org/wiki/Q1514741
concepts[16].display_name	Set (abstract data type)
concepts[17].id	https://openalex.org/C125080357
concepts[17].level	3
concepts[17].score	0.30435100197792053
concepts[17].wikidata	https://www.wikidata.org/wiki/Q45715
concepts[17].display_name	Complete graph
concepts[18].id	https://openalex.org/C2776036281
concepts[18].level	2
concepts[18].score	0.30203598737716675
concepts[18].wikidata	https://www.wikidata.org/wiki/Q48769818
concepts[18].display_name	Constraint (computer-aided design)
concepts[19].id	https://openalex.org/C11413529
concepts[19].level	1
concepts[19].score	0.2992337644100189
concepts[19].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[19].display_name	Algorithm
concepts[20].id	https://openalex.org/C199622910
concepts[20].level	3
concepts[20].score	0.28643718361854553
concepts[20].wikidata	https://www.wikidata.org/wiki/Q1128326
concepts[20].display_name	Constraint satisfaction problem
concepts[21].id	https://openalex.org/C2781315470
concepts[21].level	2
concepts[21].score	0.2671799659729004
concepts[21].wikidata	https://www.wikidata.org/wiki/Q193623
concepts[21].display_name	Binomial (polynomial)
keywords[0].id	https://openalex.org/keywords/enumeration
keywords[0].score	0.830542802810669
keywords[0].display_name	Enumeration
keywords[1].id	https://openalex.org/keywords/chromatic-scale
keywords[1].score	0.5366489291191101
keywords[1].display_name	Chromatic scale
keywords[2].id	https://openalex.org/keywords/partition
keywords[2].score	0.5346030592918396
keywords[2].display_name	Partition (number theory)
keywords[3].id	https://openalex.org/keywords/physarum-polycephalum
keywords[3].score	0.5010971426963806
keywords[3].display_name	Physarum polycephalum
keywords[4].id	https://openalex.org/keywords/computation
keywords[4].score	0.43807253241539
keywords[4].display_name	Computation
keywords[5].id	https://openalex.org/keywords/vertex
keywords[5].score	0.41906607151031494
keywords[5].display_name	Vertex (graph theory)
keywords[6].id	https://openalex.org/keywords/feature
keywords[6].score	0.4111732542514801
keywords[6].display_name	Feature (linguistics)
keywords[7].id	https://openalex.org/keywords/graph
keywords[7].score	0.40103650093078613
keywords[7].display_name	Graph
language
locations[0].id	pmh:oai:arXiv.org:2512.07120
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/2512.07120
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/2512.07120
indexed_in	arxiv
authorships[0].author.id
authorships[0].author.orcid
authorships[0].author.display_name	Allagan, J.
authorships[0].author_position	first
authorships[0].raw_author_name	Allagan, J.
authorships[0].is_corresponding	True
authorships[1].author.id
authorships[1].author.orcid
authorships[1].author.display_name	Morgan, G.
authorships[1].author_position	middle
authorships[1].raw_author_name	Morgan, G.
authorships[1].is_corresponding	False
authorships[2].author.id
authorships[2].author.orcid
authorships[2].author.display_name	Langley, S.
authorships[2].author_position	middle
authorships[2].raw_author_name	Langley, S.
authorships[2].is_corresponding	False
authorships[3].author.id
authorships[3].author.orcid
authorships[3].author.display_name	Lopez-Bonilla, R.
authorships[3].author_position	middle
authorships[3].raw_author_name	Lopez-Bonilla, R.
authorships[3].is_corresponding	False
authorships[4].author.id
authorships[4].author.orcid
authorships[4].author.display_name	Deriglazov, V.
authorships[4].author_position	last
authorships[4].raw_author_name	Deriglazov, V.
authorships[4].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/2512.07120
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-12-11T00:00:00
display_name	Chromatic Feature Vectors for 2-Trees: Exact Formulas for Partition Enumeration with Network Applications
has_fulltext	False
is_retracted	False
updated_date	2025-12-11T00:24:52.286860
primary_topic.id	https://openalex.org/T10948
primary_topic.field.id	https://openalex.org/fields/26
primary_topic.field.display_name	Mathematics
primary_topic.score	0.2047221064567566
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/2607
primary_topic.subfield.display_name	Discrete Mathematics and Combinatorics
primary_topic.display_name	Advanced Combinatorial Mathematics
cited_by_count	0
locations_count	1
best_oa_location.id	pmh:oai:arXiv.org:2512.07120
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/2512.07120
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/2512.07120
primary_location.id	pmh:oai:arXiv.org:2512.07120
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/2512.07120
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/2512.07120
publication_date	2025-12-08
publication_year	2025
referenced_works_count	0
abstract_inverted_index.*	100
abstract_inverted_index.+	75
abstract_inverted_index.3	64
abstract_inverted_index.=	58, 73, 88, 97
abstract_inverted_index.a	38
abstract_inverted_index.k	62
abstract_inverted_index.1,	76
abstract_inverted_index.>=	63
abstract_inverted_index.VM	161
abstract_inverted_index.We	0
abstract_inverted_index.in	41, 78, 158, 163, 169
abstract_inverted_index.of	9, 67
abstract_inverted_index.or	49
abstract_inverted_index.to	121, 144
abstract_inverted_index.we	55, 85
abstract_inverted_index.For	51, 81
abstract_inverted_index.all	122
abstract_inverted_index.and	35, 71, 92, 149, 166
abstract_inverted_index.fan	82
abstract_inverted_index.for	5, 61
abstract_inverted_index.not	132
abstract_inverted_index.per	111
abstract_inverted_index.set	151
abstract_inverted_index.the	12, 68
abstract_inverted_index.two	31
abstract_inverted_index.Bell	147
abstract_inverted_index.O(n)	79
abstract_inverted_index.S(t,	101
abstract_inverted_index.each	27
abstract_inverted_index.from	22
abstract_inverted_index.k-1)	60, 102
abstract_inverted_index.uses	29
abstract_inverted_index.with	103
abstract_inverted_index.These	16
abstract_inverted_index.While	131
abstract_inverted_index.avoid	46
abstract_inverted_index.cloud	164
abstract_inverted_index.fault	156
abstract_inverted_index.graph	24, 134
abstract_inverted_index.kind)	70
abstract_inverted_index.prove	56
abstract_inverted_index.these	136
abstract_inverted_index.theta	52
abstract_inverted_index.time.	80
abstract_inverted_index.under	11
abstract_inverted_index.where	26, 44
abstract_inverted_index.which	117
abstract_inverted_index.O(n^2)	109
abstract_inverted_index.Phi_n,	84
abstract_inverted_index.S(n-2,	59
abstract_inverted_index.Unlike	113
abstract_inverted_index.assign	118
abstract_inverted_index.derive	21, 93
abstract_inverted_index.graphs	53, 83
abstract_inverted_index.second	69
abstract_inverted_index.2-trees	10
abstract_inverted_index.2^(n-2)	74
abstract_inverted_index.F_{n+1}	89
abstract_inverted_index.arising	40
abstract_inverted_index.capture	138
abstract_inverted_index.colors,	32
abstract_inverted_index.exactly	30
abstract_inverted_index.feature	7
abstract_inverted_index.include	154
abstract_inverted_index.numbers	66
abstract_inverted_index.provide	127
abstract_inverted_index.rainbow	36
abstract_inverted_index.systems	43
abstract_inverted_index.through	142
abstract_inverted_index.vectors	8
abstract_inverted_index.2-trees,	124
abstract_inverted_index.Theta_n,	54
abstract_inverted_index.binomial	106
abstract_inverted_index.complete	47, 133
abstract_inverted_index.explicit	94
abstract_inverted_index.features	20, 120, 137
abstract_inverted_index.formulas	4, 95
abstract_inverted_index.n-vertex	123
abstract_inverted_index.numbers)	91
abstract_inverted_index.numbers,	148
abstract_inverted_index.triangle	14, 28
abstract_inverted_index.(Stirling	65
abstract_inverted_index.Byzantine	155
abstract_inverted_index.Fibonacci	145
abstract_inverted_index.a_{n-1,t}	99
abstract_inverted_index.achieving	108
abstract_inverted_index.chromatic	6, 115
abstract_inverted_index.classical	114
abstract_inverted_index.colorings	25
abstract_inverted_index.establish	1, 86
abstract_inverted_index.features.	130
abstract_inverted_index.identical	119
abstract_inverted_index.networks,	160
abstract_inverted_index.protocols	168
abstract_inverted_index.tolerance	157
abstract_inverted_index.(Fibonacci	90
abstract_inverted_index.allocation	162
abstract_inverted_index.component.	112
abstract_inverted_index.components	45
abstract_inverted_index.computable	18, 77, 105
abstract_inverted_index.computing,	165
abstract_inverted_index.constraint	39
abstract_inverted_index.forbidding	33
abstract_inverted_index.isolation.	50
abstract_inverted_index.meaningful	139
abstract_inverted_index.properties	141
abstract_inverted_index.r_2(Phi_n)	87
abstract_inverted_index.r_k(Phi_n)	96
abstract_inverted_index.structural	19, 129, 140
abstract_inverted_index.triangles,	37
abstract_inverted_index.bichromatic	13, 125
abstract_inverted_index.closed-form	2
abstract_inverted_index.computation	110
abstract_inverted_index.connections	143
abstract_inverted_index.constrained	23
abstract_inverted_index.constraint.	15
abstract_inverted_index.constraints	126
abstract_inverted_index.distributed	42, 170
abstract_inverted_index.efficiently	17, 104
abstract_inverted_index.enumeration	3
abstract_inverted_index.independent	150
abstract_inverted_index.informative	128
abstract_inverted_index.invariants,	135
abstract_inverted_index.Applications	153
abstract_inverted_index.enumeration.	152
abstract_inverted_index.hierarchical	159
abstract_inverted_index.polynomials,	116, 146
abstract_inverted_index.r_2(Theta_n)	72
abstract_inverted_index.r_k(Theta_n)	57
abstract_inverted_index.coefficients,	107
abstract_inverted_index.concentration	48
abstract_inverted_index.cryptography.	171
abstract_inverted_index.monochromatic	34
abstract_inverted_index.secret-sharing	167
abstract_inverted_index.sum_{t=k-1}^{n-1}	98
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	5
citation_normalized_percentile.value	0.89764041
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	True