nach oben

Journal of Combinatorial Optimization

Erschienen in:

20.02.2016

Equitable vertex arboricity of 5-degenerate graphs

verfasst von: Guantao Chen, Yuping Gao, Songling Shan, Guanghui Wang, Jianliang Wu

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

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Wu et al. (Discret Math 313:2696–2701, 2013) conjectured that the vertex set of any simple graph G can be equitably partitioned into m subsets so that each subset induces a forest, where \(\Delta (G)\) is the maximum degree of G and m is an integer with \(m\ge \lceil \frac{\Delta (G)+1}{2}\rceil \). This conjecture is verified for 5-degenerate graphs in this paper.

Vorheriger Artikel On the vertex cover problem parameterized by treewidth

Nächster Artikel Multi-agent scheduling on a single machine with a fixed number of competing agents to minimize the weighted sum of number of tardy jobs and makespans

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

Chartrand G, Kronk HV (1969) The point-arboricity of planar graphs. J Lond Math Soc 44:612–616MathSciNetCrossRefMATH

Chen BL, Lih KW, Wu PL (1994) Equitable coloring and the maximum degree. Eur J Combin 15(5):443–447MathSciNetCrossRefMATH

Chen BL, Yen CH (2012) Equitable \(\Delta \)-coloring of graphs. Discret Math 312(9):1512–1517MathSciNetCrossRefMATH

Erdős P (1964) Problem 9. Theory of graphs and its applications. Czech Acad. Sci. Publ, Prague, p 159

Esperet L, Lemoine L, Maffray F (2015) Equitable partition of graphs into induced forests. Discret Math 338(8):1481–1483MathSciNetCrossRefMATH

Hajnal A, Szemerédi (1970) Proof of a conjecture of P. Erdős. In: Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), North-Holland, Amsterdam, pp 601–623, 1970

Kierstead HA, Kostochka AV (2008) A short proof of the Hajnal-Szemerédi theorem on equitable colouring. Comb Probab Comput 17(2):265–270CrossRefMATH

Kierstead HA, Kostochka AV (2012) Every 4-colorable graph with maximum degree 4 has an equitable 4-coloring. J Graph Theory 71(1):31–48MathSciNetCrossRefMATH

Kronk HV, Mitchem J (1975) Critical point-arboritic graphs. J Lond Math Soc. (2), 9:459–466, 1974/75

Lih KW, Wu PL (1996) On equitable coloring of bipartite graphs. Discret Math. 151(1–3):155–160. Graph theory and combinatorics (Manila, 1991)

Meyer W (1973) Equitable coloring. Am Math Mon 80:920–922MathSciNetCrossRefMATH

Nakprasit K (2012) Equitable colorings of planar graphs with maximum degree at least nine. Discret Math 312(5):1019–1024MathSciNetCrossRefMATH

Wu JL, Zhang X, Li HL (2013) Equitable vertex arboricity of graphs. Discret Math 313(23):2696–2701MathSciNetCrossRefMATH

Yap HP, Zhang Y (1997) The equitable \(\Delta \)-colouring conjecture holds for outerplanar graphs. Bull Inst Math Acad Sin 25(2):143–149MathSciNetMATH

Zhang X (2015) Equitable vertex arboricity of planar graphs. Taiwan J Math 19(1):123–131MathSciNetCrossRefMATH

Zhang X, Wu JL (2011) On equitable and equitable list colorings of series-parallel graphs. Discret Math 311(10–11):800–803MathSciNetCrossRefMATH

Zhang X, Wu JL (2014) A conjecture on equitable vertex arboricity of graphs. FILOMAT 28:217–219MathSciNetCrossRefMATH

Zhang Y, Yap HP (1998) Equitable colorings of planar graphs. J Comb Math Comb Comput 27:97–105MathSciNetMATH

Titel: Equitable vertex arboricity of 5-degenerate graphs
verfasst von: Guantao Chen
Yuping Gao
Songling Shan
Guanghui Wang
Jianliang Wu
Publikationsdatum: 20.02.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-016-9997-8

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/2017

Matching and domination numbers in r-uniform hypergraphs

On Motzkin–Straus type results for non-uniform hypergraphs

Online scheduling to minimize the total weighted completion time plus the rejection cost

A note on orientation and chromatic number of graphs

Fractional matching preclusion of graphs

Recoverable robust spanning tree problem under interval uncertainty representations