nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.02.2016

Acyclic 3-coloring of generalized Petersen graphs

verfasst von: Enqiang Zhu, Zepeng Li, Zehui Shao, Jin Xu, Chanjuan Liu

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

An acyclic \(k\)-coloring of a graph \(G\) is a \(k\)-coloring of its vertices such that no cycle of \(G\) is bichromatic. \(G\) is called acyclically \(k\)-colorable if it admits an acyclic \(k\)-coloring. In this paper, we prove that the generalized Petersen graph \(P(n,k)\) is acyclically 3-colorable except \(P(4,1)\) and the classical Petersen graph \(P(5,2)\).

Vorheriger Artikel A sufficient condition for a tree to be --totally labelable

Nächster Artikel Degree conditions for weakly geodesic pancyclic graphs and their exceptions

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

Albertson MO, Berman DM (1977) Every planar graph has an acyclic 7-coloring. Israel J Math 28:169–174MathSciNetCrossRefMATH

Angelini P, Frati F (2012) Acyclically 3-colorable planar graphs. J Comb Optim 24:116–130MathSciNetCrossRefMATH

Bondy JA, Murty USR (2008) Graph theory. Springer, New YorkCrossRefMATH

Borodin OV (1976) A proof of grünbaum’s conjecture on the acyclic 5-colorability of planar graphs. Dokl Akad Nauk SSSR 231:18–20MathSciNet

Boyer JM, Myrvold WJ (2004) On the cutting edge: Simplified \(o(n)\) planarity by edge addition. J Graph Algorithm Appl 3(8):241–273MathSciNetCrossRef

Cheng C, McDermid E, Suzuki I (2011) Planarization and acyclic colorings of subcubic claw-free graphs. Graph-theoretic concepts in computer science. In Proceedings of the 37th international workshop, WG 2011, Teplá Monastery, June 21–24

Coleman TF, Cai JY (1986) The cyclic coloring problem and estimation of sparse hessian matrices. SIAM J Algebraic Discret Methods 7:221–235MathSciNetCrossRefMATH

Dujmović V, Morin P, Wood DR (2005) Layout of graphs with bounded tree-width. SIAM J Comput 34:553–579MathSciNetCrossRefMATH

Fertin G, Godard E, Raspaud A (2002) Minimum feedback vertex set and acyclic coloring. Inform Process Lett 84:131–139MathSciNetCrossRefMATH

Gebremedhin AH, Tarafdar A, Pothen A, Walther A (2009) Efficient computation of sparse hessians using coloring and automatic differentiation. Inform J Comput 21:209–223MathSciNetCrossRefMATH

Grünbaum B (1973) Acyclic colorings of planar graphs. Israel J Math 14:390–408MathSciNetCrossRefMATH

Kostochka AV (1976) Acyclic 6-coloring of planar graphs. Metody Diskret Anal 28:40–56MATH

McKay BD (2013) Nauty user’s guide. Computer Science Department, Australian National University, Software available from http://cs.anu.edu.au/~bdm/nauty. Accessed 3 July 2013

Mitchem J (1974) Every planar graph has an acyclic 8-coloring. Duke Math J 41:177–181MathSciNetCrossRefMATH

Mondal D, Nishat RI, Rahman MS, Whitesides S (2013) Acyclic coloring with few division vertices. J Discret Algorithms 23:42–53

Mondal D, Nishat RI, Whitesides S, Rahman MS (2012) Acyclic coloring of graph subdivisions revisited. J Discret Algorithms 16:90–103

Ochem P (2005) Negative results on acyclic improper colorings. In Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb’05), pp. 357–362

Watkins ME (1969) A theorem on tait colorings with an application to the generalized petersen graphs. J Combin Theory 6:152–164

Titel: Acyclic 3-coloring of generalized Petersen graphs
verfasst von: Enqiang Zhu
Zepeng Li
Zehui Shao
Jin Xu
Chanjuan Liu
Publikationsdatum: 01.02.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2016
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-014-9799-9

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 2/2016

Team selection for prediction tasks

Improved approximations for buy-at-bulk and shallow-light -Steiner trees and -subgraph

Connection between a class of polynomial optimization problems and maximum cliques of non-uniform hypergraphs

On single machine scheduling with resource constraint

Degree-constrained orientations of embedded graphs

Integral packing of branchings in capacitaded digraphs

Premium Partner