Metraipolis › archive › dc_485fc25d984f
Adjacent-vertex-distinguishing-total coloring — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Adjacent-vertex-distinguishing-total_coloring
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-07T14:37:13.293Z
- SHA-256 of the archived text
8d33ad2d6cacf953ef2b2e2d4855b192f6463a224e5471183f93586a394d4c23- Stable URL of this page
https://metraipolis.com/documento/dc_485fc25d984f
How to cite
Adjacent-vertex-distinguishing-total coloring — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Adjacent-vertex-distinguishing-total_coloring (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_485fc25d984f (Metraipolis archive dc_485fc25d984f, sha256 8d33ad2d6cacf953ef2b2e2d4855b192f6463a224e5471183f93586a394d4c23)
BibTeX
@misc{dc485fc25d984f,
title = {Adjacent-vertex-distinguishing-total coloring — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Adjacent-vertex-distinguishing-total_coloring},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_485fc25d984f; sha256 8d33ad2d6cacf953ef2b2e2d4855b192f6463a224e5471183f93586a394d4c23},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Adjacent-vertex-distinguishing-total_coloring. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In graph theory, a total coloring is a coloring on the vertices and edges of a graph such that: (1). no adjacent vertices have the same color; (2). no adjacent edges have the same color; and (3). no edge and its endvertices are assigned the same color. In 2005, Zhang et al. added a restriction to the definition of total coloring and proposed a new type of coloring defined as follows. Let G = (V,E) be a simple graph endowed with a total coloring φ, and let u be a vertex of G. The set of colors that occurs in the vertex u is defined as C(u) = {φ(u)} ∪ {φ(uv) | uv ∈ E(G)}. Two vertices u,v ∈ V(G) are distinguishable if their color-sets are distinct, i.e., C(u) ≠ C(v). In graph theory, a total coloring is an adjacent-vertex-distinguishing-total-coloring (AVD-total-coloring) if it has the following additional property: (4). for every two adjacent vertices u,v of a graph G, their colors-sets are distinct from each other, i.e., C(u) ≠ C(v). The adjacent-vertex-distinguishing-total-chromatic number χat(G) of a graph G is the fewest colors needed in an AVD-total-coloring of G. The following lower bound for the AVD-total chromatic number can be obtained from the definition of AVD-total-coloring: If a simple graph G has two adjacent vertices of maximum degree, then χat(G) ≥ Δ(G) + 2. Otherwise, if a simple graph G does not have two adjacent vertices of maximum degree, then χat(G) ≥ Δ(G) + 1. In 2005, Zhang et al. determined the AVD-total-chromatic number for some classes of graphs, and based in their results they conjectured the following. AVD-Total-Coloring Conjecture. (Zhang et al.) χat(G) ≤ Δ(G) + 3. The AVD-Total-Coloring Conjecture is known to hold for some classes of graphs, such as complete graphs, graphs with Δ=3, and all bipartite graphs. In 2012, Huang et al. showed that χat(G) ≤ 2Δ(G) for any simple graph G with maximum degree Δ(G) > 2. In 2014, Papaioannou and Raftopoulou described an algorithmic procedure that gives a 7-AVD-total-colouring for any 4-regular graph.
Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in inglese, in ordine alfabetico).
Fonte: Wikipedia in inglese, voce «Adjacent-vertex-distinguishing-total coloring» — https://en.wikipedia.org/wiki/Adjacent-vertex-distinguishing-total_coloring
Wikidata Q17005461: «type of total coloring in graph theory» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q17005461
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Adjacent-vertex-distinguishing-total_coloring?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1300005955, consultata il 2026-11-07T14:32:23.631Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 24394d82265322f317db72cebf06b333ddac5b32a77dea4bedb682e7c8269976