On cliques of signed and switchable signed graphs
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
Vertex coloring of a graph G with n-colors can be equivalently thought to be a graph homomorphism (edge preserving vertex mapping) of G to the complete graph Kn of order n. So, in that sense, the χ(G) of G will be the order of the smallest complete graph to which G admits a homomorphism to. As every graph, which is not a complete graph, admits a homomorphism to a smaller complete graph, we can redefine the χ(G) of G to be the order of the smallest graph to which G admits a homomorphism to. Of course, such a smallest graph must be a complete graph as they are the only graphs with equal to their order. The concept of vertex coloring can be generalize for other types of graphs, namely, oriented graphs (directed graphs with no cycle of length 1 or 2), 2-edge-colored or signed graphs (graphs with positive or negative signs assigned to each edge) and switchable signed graphs (equivalence class of signed graph with respect to switching signs of edges incident to the same vertex) using the notion of graph homomorphism. Naturally, the is defined to be the order of the smallest graph (of the same type) to which a graph admits homomorphism to. For the above mentioned type of graphs, the graphs with smallest order, that is, the graphs with order equal to their (so defined) chromatic number are called ocliques, scliques and [s]-cliques respectively. These cliques turns out to be much more complicated than their undirected counterpart and are interesting objects of study. In this article, we mainly study different aspects of cliques for signed and switchable signed graphs. In particular, we show that it is NP-hard to decide if edges of a given undirected graph can be assigned positive and negative signatures such that it becomes an sclique or an [s]-clique. We also show that, asymptotically, almost all signed graphs are scliques or [s]-cliques. Furthermore, we prove a sufficient and necessary condition for a signed graph (or switchable signed graph) to be an sclique (or [s]-clique). We study the of vertices that an sclique (or [s]-clique) can have when their underlying graph is planar and prove a tight upper bound of 15. We also study the same for outerplanar graphs and planar graphs with given girth (length of the smallest cycle). Finally, we generalize the concept of cliques for n-edge-colored graphs (graphs with one among n different colors assigned to each of its edge) and do a similar study for outerplanar and planar graphs.
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.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.000 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 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