nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.08.2016

An improved bound on 2-distance coloring plane graphs with girth 5

verfasst von: Wei Dong, Wensong Lin

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

A vertex coloring is called \(2\)-distance if any two vertices at distance at most \(2\) from each other get different colors. The minimum number of colors in 2-distance colorings of \(G\) is its 2-distance chromatic number, denoted by \(\chi _2(G)\). Let \(G\) be a plane graph with girth at least \(5\). In this paper, we prove that \(\chi _2(G)\le \Delta +8\) for arbitrary \(\Delta (G)\), which partially improves some known results.

Vorheriger Artikel A note on the duality between matchings and vertex covers in balanced hypergraphs

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

Bondy JA, Murty USR (1976) Graph theory with applications. Macmillan Ltd. Press, New YorkCrossRefMATH

Borodin OV, Broersma H, Glebov A, van den Heuvel J (2002) Stars and bunches in planar graphs. General planar graphs and colourings. CDAM Researches Report Part II

Borodin OV, Ivanova AO (2009) 2-Distance \(\Delta +2\)-coloring of planar graphs with girth six and \(\Delta \ge 18\). Discret Math 309:6496–6502MathSciNetCrossRefMATH

Borodin OV, Ivanova AO, Neustroeva TK (2004) 2-Distance coloring of sparse plane graphs. Sib Èlektron Math Izv 1:76–90 (in Russian)MathSciNetMATH

Borodin OV, Glebov AN, Ivanova AO, Neustroeva TK, Tashkinov VA (2004) Sufficient conditions for the 2-distance \(\Delta +1\)-colorability of plane graphs. Sib lektron Math Izv 1:129–141 (in Russian)MathSciNetMATH

Bu Y, Zhu X (2012) An optimal square coloring of planar graphs. J Comb Optim 24:580–592MathSciNetCrossRefMATH

Bu Y, Yan X (2014) List 2-distance coloring of planar graphs. J Comb Optim doi:10.1007/s10878-013-9700-2

Charpentier C, Montassier M, Raspaud A (2013) L(p, q)-labeling of sparse graphs. J Comb Optim 25:646–660MathSciNetCrossRefMATH

Dvořàk Z, Kràl D, Nejedlỳ P, Škrekovski R (2008) Coloring squares of planar graphs with girth six. Eur J Comb 29:838–849MathSciNetCrossRefMATH

Molloy M, Salavatipour MR (2005) A bound on the chromatic number of the square of a planar graph. J Comb Theory Ser B 94:189–213MathSciNetCrossRefMATH

van den Heuvel J, McGuinness S (2003) Coloring of the square of planar graph. J Graph Theory 42:110–124MathSciNetCrossRefMATH

Wang W, Lih K (2003) Labeling planar graphs with conditions on girth and distance two. SIAM J Discret Math 17(2):264–275MathSciNetCrossRefMATH

Wegner G (1977) Graphs with given diameter and a coloring problem, Technical Report, University of Dortmund, Germany

Titel: An improved bound on 2-distance coloring plane graphs with girth 5
verfasst von: Wei Dong
Wensong Lin
Publikationsdatum: 01.08.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-015-9888-4

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

Multi-neighborhood based path relinking for two-sided assembly line balancing problem

Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem

Tabu search for the real-world carpooling problem

Multi-start iterated tabu search for the minimum weight vertex cover problem

A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang

Total and paired domination numbers of bundles over a cycle