Top

Journal of Combinatorial Optimization

Published in:

22-10-2019

Neighbor-distinguishing total coloring of planar graphs with maximum degree twelve

Authors: Jingjing Huo, Yiqiao Wang, Weifan Wang, Wenjing Xia

Published in: Journal of Combinatorial Optimization | Issue 1/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The neighbor-distinguishing total chromatic number \(\chi ''_{a}(G)\) of a graph G is the minimum number of colors required for a proper total coloring of G such that any two adjacent vertices have different sets of colors. In this paper, we show that if G is a planar graph with \(\Delta =12\), then \(13\le \chi ''_{a}(G)\le 14\), and moreover \(\chi ''_{a}(G)=14\) if and only if G contains two adjacent 12-vertices.

previous article Efficient algorithms for measuring the funnel-likeness of DAGs

next article On the König deficiency of zero-reducible graphs

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Alon N (1999) Combinatorial Nullstellensatz. Comb Probab Comput 8:7–29MathSciNetCrossRef

Chen X (2008) On the adjacent vertex distinguishing total coloring numbers of graphs with \(\Delta =3\). Discrete Math 308:4003–4007MathSciNetCrossRef

Cheng X, Wang G, Wu J (2017) The adjacent vertex distinguishing total chromatic numbers of planar graphs with \(\Delta =10\). J Comb Optim 34:383–397MathSciNetCrossRef

Coker T, Johannson K (2012) The adjacent vertex distinguishing total chromatic number. Discrete Math 312:2741–2750MathSciNetCrossRef

Huang D, Wang W (2012) Adjacent vertex distinguishing total colorings of planar graphs with large maximum degree. Sci Sin Math 42:151–164CrossRef

Huang D, Wang W, Yan C (2012) A note on the adjacent vertex distinguishing total chromatic number of graphs. Discrete Math 312:3544–3546MathSciNetCrossRef

Hulgan J (2009) Concise proofs for adjacent vertex-distinguishing total colorings. Discrete Math 309:2548–2550MathSciNetCrossRef

Huo J, Wang W, Wang Y (2018) A characterization for the neighbor-distinguishing total chromatic number of planar graphs with \(\Delta =13\). Discrete Math 314:3044–3056MathSciNetCrossRef

Lu Y, Li J, Luo R, Miao Z (2017) Adjacent vertex distinguishing total coloring of graphs with maximum degree 4. Discrete Math 340:119–123MathSciNetCrossRef

Luiz A, Campos C, de Mello C (2017) AVD-total-chromatic number of some families of graphs with \(\Delta (G)=3\). Discrete Appl Math 217:628–638MathSciNetCrossRef

Papaioannou A, Raftopoulou C (2014) On the AVDTC of 4-regular graphs. Discrete Math 330:20–40MathSciNetCrossRef

Vučković B (2018) An improved upper bound on the adjacent vertex distinguishing total chromatic number of graphs. Discrete Math 341:1472–1478MathSciNetCrossRef

Wang H (2007) On the adjacent vertex distinguishing total chromatic number of the graphs with \(\Delta (G)=3\). J Comb Optim 14:87–109MathSciNetCrossRef

Wang W, Huang D (2014) The adjacent vertex distinguishing total coloring of planar graphs. J Comb Optim 27:379–396MathSciNetCrossRef

Wang W, Huo J, Huang D, Wang Y (2019) Planar graphs with \(\Delta =9\) are neighbor-distinguishing totally 12-colorable. J Comb Optim 37:1071–1089MathSciNetCrossRef

Yang D, Sun L, Yu X, Wu J, Zhou S (2017) Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10. Appl Math Comput 314:456–468MathSciNetMATH

Zhang Z, Chen X, Li J, Yao B, Lu X, Wang J (2005) On adjacent-vertex-distinguishing total coloring of graphs. Sci China Ser A 48:289–299MathSciNetCrossRef

Title: Neighbor-distinguishing total coloring of planar graphs with maximum degree twelve
Authors: Jingjing Huo
Yiqiao Wang
Weifan Wang
Wenjing Xia
Publication date: 22-10-2019
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2020
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00465-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2020

Approximation algorithms for two-stage flexible flow shop scheduling

Neighbor sum distinguishing total colorings of IC-planar graphs with maximum degree 13

Dynamic three-stage operating room scheduling considering patient waiting time and surgical overtime costs

Less is more approach for competing groups scheduling with different learning effects

Approximation algorithm for a generalized Roman domination problem in unit ball graphs

The structure of graphs with given number of blocks and the maximum Wiener index

Premium Partner