Bibliographic record
Abstract
The adjacent-vertex-distinguishing-total-colouring (AVD-total-colouring) problem was introduced and studied by Zhang et al. around 2005.This problem consists in associating colours to the vertices and edges of a graph G = (V (G), E(G)) using the least number of colours, such that: (i) any two adjacent vertices or adjacent edges receive distinct colours; (ii) each vertex receive a colour different from the colours of its incident edges; and (iii) for any two adjacent vertices u, v ∈ V (G), the set of colours that color u and its incident edges is distinct from the set of colours that color v and its incident edges.The smallest number of colours for which a graph G admits an AVD-total-colouring is named its AVDtotal chromatic number.Zhang et al. determined the AVD-total chromatic number for some classical families of graphs and noted that all of them admit an AVD-total-colouring with no more than ∆(G) + 3 colours.Based on this observation, the authors conjectured that ∆(G) + 3 colours would be sufficient to construct an AVD-total-colouring for any simple graph G.This conjecture is called the AVD-Total-Colouring Conjecture and remains open for arbitrary graphs, having been verified for a few families of graphs.In this dissertation, we present an overview of the main existing results related to the AVD-total-colouring of graphs.Furthermore, we determine the AVD-total-chromatic number for the following families of graphs: simple graphs with ∆(G) = 3 and without adjacent vertices of maximum degree; flower-snarks; Goldberg snarks; generalized Blanuša snarks; Loupekine snarks; and complete equipartite graphs of even order.We verify that the graphs of these families have AVD-total-chromatic number at most ∆(G) + 2. Additionally, we verify that the AVD-Total-Colouring Conjecture is true for tripartite graphs and complete equipartite graphs of odd order.These results confirm the validity of the AVD-Total-Colouring Conjecture for all the families considered in this dissertation.ix Resumo O problema da coloração total semiforte foi introduzido por Zhang et al. por volta de 2005.Este problema consiste em associar cores às arestas e aos vértices de um grafo G = (V (G), E(G)), utilizando o menor número de cores possível, de forma que: (i) quaisquer dois vértices ou duas arestas adjacentes possuam cores distintas; (ii) cada vértice tenha cor diferente das cores das arestas que nele incidem; e, além disso, (iii) para quaisquer dois vértices adjacentes u, v ∈ V (G), o conjunto das cores que colorem u e suas arestas incidentes é distinto do conjunto das cores que colorem v e suas arestas incidentes.Denominamos esse menor número de cores para o qual um grafo admite uma coloração total semiforte como número cromático total semiforte.Zhang et al. também determinaram o número cromático total semiforte de algumas famílias clássicas de grafos e observaram que todas elas possuem uma coloração total semiforte com no máximo ∆(G) + 3 cores.Com base nesta observação, eles conjeturaram que ∆(G) + 3 cores seriam suficientes para construir uma coloração total semiforte para qualquer grafo simples G. Essa conjetura é denominada Conjetura da Coloração Total Semiforte e permanece aberta para grafos arbitrários, tendo sido verificada apenas para algumas famílias de grafos.Nesta dissertação, apresentamos uma resenha dos principais resultados existentes envolvendo a coloração total semiforte.Além disso, determinamos o número cromático total semiforte para as seguintes famílias: os grafos simples com ∆(G) = 3 e sem vértices adjacentes de grau máximo; os snarks-flor; os snarks de Goldberg; os snarks de Blanuša generalizados; os snarks de Loupekine LP 1 ; e os grafos equipartidos completos de ordem par.Verificamos que os grafos destas famílias possuem número cromático total semiforte menor ou igual a ∆(G) + 2. Investigamos também a coloração total semiforte dos grafos tripartidos e dos grafos equipartidos completos de ordem ímpar e verificamos que os grafos destas famílias possuem número cromático total semiforte menor ou igual a ∆(G) + 3. Os resultados obtidos confirmam a validade da Conjetura da Coloração Total Semiforte para todas as famílias consideradas nesta dissertação.
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.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.004 | 0.021 |
| Meta-epidemiology (narrow) | 0.002 | 0.001 |
| Meta-epidemiology (broad) | 0.002 | 0.003 |
| Bibliometrics | 0.002 | 0.003 |
| Science and technology studies | 0.005 | 0.007 |
| Scholarly communication | 0.007 | 0.009 |
| Open science | 0.002 | 0.005 |
| Research integrity | 0.003 | 0.009 |
| Insufficient payload (model declined to judge) | 0.011 | 0.002 |
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 itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".