nach oben

Journal of Combinatorial Optimization

Erschienen in:

23.08.2018

Planar graphs with \(\Delta =9\) are neighbor-distinguishing totally 12-colorable

verfasst von: Weifan Wang, Jingjing Huo, Danjun Huang, Yiqiao Wang

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The neighbor-distinguishing total coloring of a graph G is a proper total coloring of G using k colors such that any two adjacent vertices have different sets of colors. It was known that every planar graph G with \(\Delta \ge 10\) is neighbor-distinguishing totally \((\Delta +3)\)-colorable. In this paper, we extend this result to the case \(\Delta =9\). Namely, we prove that every planar graph G with \(\Delta =9\) is neighbor-distinguishing totally 12-colorable.

Vorheriger Artikel Approximation algorithms for the graph balancing problem with two speeds and two job lengths

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Nur mit Berechtigung zugänglich

Alon N (1999) Combinatorial nullstellensatz. Comb Probab Comput 8:7–29CrossRef

Appel K, Haken W (1976) Every planar map is four colourable. Bull Am Math Soc 82:711–712CrossRefMATH

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

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–397MathSciNetCrossRefMATH

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

Grötzsch H (1959) Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel. Wiss Z Martin Luther-Univ Halle Wittenberg, Math-Nat Reihe 8:109–120MathSciNet

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

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

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

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

Sanders D, Zhao Y (2001) Planar graphs of maximum degree seven are Class I. J Comb Theory Ser B 83:201–212MathSciNetCrossRefMATH

Vizing VG (1964) On an estimate of the chromatic index of a p-graph. Diskret Anal 3:25–30

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

Wang W, Wang Y (2008) Adjacent vertex distinguishing total coloring of graphs with lower average degree. Taiwanese J Math 12:979–990MathSciNetCrossRefMATH

Wang W, Wang P (2009) On adjacent-vertex-distinguishing total coloring of \(K_{4}\)-minor free graphs. Sci China Ser A 39:1462–1472

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

Wang Y, Wang W (2010) Adjacent vertex distinguishing total colorings of outerplanar graphs. J Comb Optim 19:123–133MathSciNetCrossRefMATH

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–299MathSciNetCrossRefMATH

Titel: Planar graphs with are neighbor-distinguishing totally 12-colorable
verfasst von: Weifan Wang
Jingjing Huo
Danjun Huang
Yiqiao Wang
Publikationsdatum: 23.08.2018
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2019
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-018-0334-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2019

Operating room planning and surgical case scheduling: a review of literature

A note on a two-agent scheduling problem related to the total weighted late work

Minimum rank and zero forcing number for butterfly networks

Restricted power domination and zero forcing problems

Competitive analysis of randomized online strategies for the multi-agent k-Canadian Traveler Problem

Client assignment problems for latency minimization

Premium Partner