- Notes
- References
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.[1] 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 least number of 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.[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.[3]) χat(G) ≤ Δ(G) + 3. The AVD-Total-Coloring Conjecture is known to hold for some classes of graphs, such as complete graphs,[4] graphs with Δ=3,[5][6] and all bipartite graphs.[7] In 2012, Huang et al.[8] showed that χat(G) ≤ 2Δ(G) for any simple graph G with maximum degree Δ(G) > 2. In 2014, Papaioannou and Raftopoulou[9] described an algorithmic procedure that gives a 7-AVD-total-colouring for any 4-regular graph. Notes 1. ^Zhang 2005.
2. ^Zhang 2005, p. 290.
3. ^Zhang 2005, p. 299.
4. ^Hulgan 2009, p. 2.
5. ^Hulgan 2009, p. 2.
6. ^Chen 2008.
7. ^Zhang 2005.
8. ^Huang2012
9. ^Papaioannou2014
References - {{cite journal | last1 = Zhang | first1 = Zhong-fu | last2 = Chen | first2 = Xiang-en | last3 = Li | first3 = Jingwen | last4 = Yao | first4 = Bing | last5 = Lu | first5 = Xinzhong | last6 = Wang | first6 = Jianfang | year = 2005 | title = On adjacent-vertex-distinguishing total coloring of graphs | url = | journal = Science China Mathematics | volume = 48 | issue = 3 | pages = 289–299 | doi = 10.1360/03ys0207}}
- {{cite journal | last1 = Hulgan | first1 = Jonathan | year = 2009 | title = Concise proofs for adjacent vertex-distinguishing total colorings | url = | journal = Discrete Mathematics | volume = 309 | issue = 8 | pages = 2548–2550 | doi = 10.1016/j.disc.2008.06.002 }}
- {{cite journal | last1 = Chen | first1 = Xiang'en | year = 2008 | title = On the adjacent vertex distinguishing total coloring numbers of graphs with Delta=3 | url = | journal = Discrete Mathematics | volume = 308 | issue = 17| pages = 4003–4007 | doi = 10.1016/j.disc.2007.07.091 }}
- {{cite journal | last1 = Huang | first1 = D. | last2 = Wang | first2 = W. | last3 = Yan | first3 = C. | year = 2012 | title = A note on the adjacent vertex distinguishing total chromatic number of graphs | url = | journal = Discrete Mathematics | volume = 312 | issue = 24 | pages = 3544–3546 | doi = 10.1016/j.disc.2012.08.006 }}
- {{cite journal | last1 = Chen | first1 = Meirun | last2 = Guo | first2 = Xiaofeng | year = 2009 | title = Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes | url = | journal = Information Processing Letters | volume = 109 | issue = 12 | pages = 599–602 | doi = 10.1016/j.ipl.2009.02.006 }}
- {{cite journal | last1 = Wang | first1 = Yiqiao | last2 = Wang | first2 = Weifan | year = 2010 | title = Adjacent vertex distinguishing total colorings of outerplanar graphs | url = | journal = Journal of Combinatorial Optimization | volume = 19 | issue = 2 | pages = 123–133 | doi = 10.1007/s10878-008-9165-x }}
- {{cite journal|last1=P. de Mello |first1=Célia |last2=Pedrotti |first2=Vagner |year=2010 |title=Adjacent-vertex-distinguishing total coloring of indifference graphs |url=http://mc.sbm.org.br/edicoes/39/12_39_mc_rev_vagner_ctfgi.pdf |journal=Matematica Contemporanea |volume=39 |issue= |pages=101–110 |doi= }}{{dead link|date=June 2017 |bot=InternetArchiveBot |fix-attempted=yes }}
- {{cite journal | last1 = Wang | first1 = Weifan | last2 = Huang | first2 = Danjun | year = 2012 | title = The adjacent vertex distinguishing total coloring of planar graphs | url = | journal = Journal of Combinatorial Optimization | volume = 27| issue = 2| pages = 379| doi = 10.1007/s10878-012-9527-2}}
- {{cite journal | last1 = Chen | first1 = Xiang-en | last2 = Zhang | first2 = Zhong-fu | year = 2008 | title = AVDTC numbers of generalized Halin graphs with maximum degree at least 6 | url = | journal = Acta Mathematicae Applicatae Sinica | volume = 24 | issue = 1 | pages = 55–58 | doi = 10.1007/s10878-012-9527-2}}
- {{cite journal | last1 = Huang | first1 = Danjun | last2 = Wang | first2 = Weifan | last3 = Yan | first3 = Chengchao | year = 2012 | title = A note on the adjacent vertex distinguishing total chromatic number of graphs | url = | journal = Discrete Mathematics | volume = 312 | issue = 24 | pages = 3544–3546 | doi = 10.1016/j.disc.2012.08.006}}
- {{cite journal | last1 = Papaioannou | first1 = A. | last2 = Raftopoulou | first2 = C. | year = 2014 | title = On the AVDTC of 4-regular graphs | url = | journal = Discrete Mathematics | volume = 330 | issue = | pages = 20–40 | doi = 10.1016/j.disc.2014.03.019}}
- {{cite journal | last1 = Luiz | first1 = Atílio G. | last2 = Campos | first2 = C.N. | last3 = de Mello | first3 = C.P. | year = 2015 | title = AVD-total-colouring of complete equipartite graphs | url = | journal = Discrete Applied Mathematics | volume = 184| issue = | pages = 189| doi = 10.1016/j.dam.2014.11.006}}
1 : Graph coloring |