On a Generalization of the Gallai-Roy-Vitaver Theorem and Mathematical Programming Models for the Bandwidth Coloring Problem
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
We consider the bandwidth coloring problem, a generalization of the well-known graph coloring problem. For the latter problem, a classical theorem, discovered independently by Gallai, Roy and Vitaver, states that the chromatic number of a graph is bounded from above by the number of vertices in the longest elementary path in any directed graph derived by orienting all edges in the graph. We generalize this result to the bandwidth coloring problem. Two proofs are given, a simple one and a more complex that is based on a series of equivalent mathematical programming models. These formulations can motivate the development of various solution algorithms for the bandwidth coloring problem. Resume Nous considerons le probleme de la coloration par bande, une generalisation de la coloration usuelle des sommets d’un graphe. Pour ce dernier, un theoreme classique, enonce independamment par Gallai, Roy et Vitaver, demontre que le nombre chromatique d’un graphe est borne superieurement par le nombre de sommets sur le plus long chemin elementaire dans un graphe oriente obtenu en choisissant une orientation pour chaque arete du graphe. Nous generalisons ce resultat au probleme de la coloration par bande. Nous donnons deux preuves de ce resultat, une simple et une plus complexe qui est basee sur l’equivalence entre divers modeles de programmation mathematique pour la coloration par bande. Ces divers modeles peuvent motiver le developpement de nouveaux algorithmes pour la resolution du probleme de la coloration par bande. Les Cahiers du GERAD G–2007–22 1
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.007 | 0.002 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.001 |
| Science and technology studies | 0.001 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.001 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it