Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

21.11.2018

Conflict-free connection of trees

Zeitschrift:
Journal of Combinatorial Optimization
Autoren:
Hong Chang, Meng Ji, Xueliang Li, Jingshu Zhang
Wichtige Hinweise
Supported by NSFC Nos. 11871034, 11531011 and NSFQH No. 2017-ZJ-790.

Abstract

We study the conflict-free connection coloring of trees, which is also the conflict-free coloring of the so-called edge-path hypergraphs of trees. We first prove that for a tree T of order n, \( cfc (T)\ge cfc (P_n)=\lceil \log _{2} n\rceil \), which completely confirms the conjecture of Li and Wu [24]. We then present a sharp upper bound for the conflict-free connection number of trees by a simple algorithm. Furthermore, we show that the conflict-free connection number of the binomial tree with \(2^{k-1}\) vertices is \(k-1\). At last, we study trees which are \( cfc \)-critical, and prove that if a tree T is \( cfc \)-critical, then the conflict-free connection coloring of T is equivalent to the edge ranking of T.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Premium Partner

    Bildnachweise