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
Graph coloring has been studied for a long time and continues to receive \ninterest within the research community \\cite{kubale2004graph}. It has applications \nin scheduling \\cite{daniel2004graph}, timetables, and compiler register \nallocation \\cite{lewis2015guide}. The most popular variant of graph coloring, \nk-coloring, can be thought of as an assignment of $k$ colors to the vertices of a \ngraph such that adjacent vertices are assigned different colors. \n \nReconfiguration problems, typically defined on the solution space of search problems, \nbroadly ask whether one solution can be transformed to another solution using \nstep-by-step transformations, when constrained to one or more specific transformation \nsteps \\cite{van2013complexity}. One well-studied reconfiguration problem is the \nproblem of deciding whether one k-coloring can be transformed to another k-coloring \nby changing the color of one vertex at a time, while always maintaining a k-coloring \nat each step. \n \nWe consider two variants of graph coloring: acyclic coloring and equitable \ncoloring, and their corresponding reconfiguration problems. A k-acylic coloring is \na k-coloring where there are more than two colors used by the vertices of each \ncycle, and a k-equitable coloring is a k-coloring such that each color class, which is \ndefined as the set of all vertices with a particular color, is nearly the same \nsize as all others. \n \nWe show that reconfiguration of acyclic colorings is PSPACE-hard, and that for \nnon-bipartite graphs with chromatic number 3 there exist two k-acylic colorings \n$f_s$ and $f_e$ such that there is no sequence of transformations that can \ntransform $f_s$ to $f_e$. We also consider the problem of whether two \nk-acylic colorings can be transformed to each other in at most $\\ell$ steps, and \nshow that it is in XP, which is the class of algorithms that run in time \n$O(n^{f(k)})$ for some computable function $f$ and parameter $k$, where in this \ncase the parameter is defined to be the length of the reconfiguration sequence \nplus the length of the longest induced cycle. \n \nWe also show that the reconfiguration of equitable colorings is PSPACE-hard \nand W[1]-hard with respect to the number of vertices with the same color. We \ngive polynomial-time algorithms for Reconfiguration of Equitable Colorings when \nthe number of colors used is two and also for paths when the number of colors \nused is three.
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.001 | 0.001 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.001 | 0.000 |
| Bibliometrics | 0.001 | 0.000 |
| Science and technology studies | 0.001 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.002 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.001 | 0.001 |
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