Skip to main content
Top
Published in: Journal of Combinatorial Optimization 1/2020

25-04-2020

New restrictions on defective coloring with applications to steinberg-type graphs

Authors: Addie Armstrong, Nancy Eaton

Published in: Journal of Combinatorial Optimization | Issue 1/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Steinberg-type graphs, those planar graphs containing no 4-cycles or 5-cycles, became well known with the 1976 Steinberg Conjecture which stated that such graphs are properly 3-colorable. Recently, Steinberg’s Conjecture was demonstrated to be false (Cohen-Addad et al. in J Combin Theory Ser B 122: 452–456, 2016). However, Steinberg-type graphs are (3, 0, 0)-defective colorable (Hill et al. in Discrete Math 313:2312–2317, 2013), i. e. of the three colors, two are used properly and any vertex colored with the first color is allowed to be adjacent to up to three other veritces with the same color. In this paper, we introduce a stronger form of defective graph coloring that places limits on the permitted defects in a coloring. Using the strength of this new type of coloring, we prove the current closest result to Steinberg’s original conjecture and show that the counterexample given in Cohen-Addad et al. (J Combin Theory Ser B 122:452–456,2016) is colorable with this stronger form of defective 3-coloring.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

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!

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!

Literature
go back to reference Bopche G, Mehtrea M (2017) Graph similarity metrics for assessing temporal changes in attack surface of dynamic networks. Comput Secur 64:16–43CrossRef Bopche G, Mehtrea M (2017) Graph similarity metrics for assessing temporal changes in attack surface of dynamic networks. Comput Secur 64:16–43CrossRef
go back to reference Borodin OV, Glebov AN, Raspaud A, Salavatipour MR (2005) Planar graphs without cycles of length from 4 to 7 are 3-colorable. J Combin Theory Ser B 93:303–311MathSciNetCrossRef Borodin OV, Glebov AN, Raspaud A, Salavatipour MR (2005) Planar graphs without cycles of length from 4 to 7 are 3-colorable. J Combin Theory Ser B 93:303–311MathSciNetCrossRef
go back to reference Cohen-Addad V, Hebdigeb M, Kráil D, Lia Z, Salgadode E (2016) Steinberg’s Conjecture is False. J Combin Theory Ser B 122:452–456MathSciNetCrossRef Cohen-Addad V, Hebdigeb M, Kráil D, Lia Z, Salgadode E (2016) Steinberg’s Conjecture is False. J Combin Theory Ser B 122:452–456MathSciNetCrossRef
go back to reference Cowen LJ, Cowen RH, Woodall DR (1986) Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. J Gr Theory 10:187–195MathSciNetCrossRef Cowen LJ, Cowen RH, Woodall DR (1986) Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. J Gr Theory 10:187–195MathSciNetCrossRef
go back to reference Chen M, Wang Y, Liu P, Xu J (2016) Planar graphs without cycles of length 4 or 5 are \((2,0,0)\)-colorable. Discrete Math 339:886–905MathSciNetCrossRef Chen M, Wang Y, Liu P, Xu J (2016) Planar graphs without cycles of length 4 or 5 are \((2,0,0)\)-colorable. Discrete Math 339:886–905MathSciNetCrossRef
go back to reference Grünbaum B (1964) Grötzsch theorem on 3-colorings. Michigan Math J 10:303–310MATH Grünbaum B (1964) Grötzsch theorem on 3-colorings. Michigan Math J 10:303–310MATH
go back to reference Jensen T, Toft B (1995) Gr Color Probl. Wiley, New York Jensen T, Toft B (1995) Gr Color Probl. Wiley, New York
go back to reference Miao Z, Wang Y, Xu L (2014) Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\)-colorable. J Comb Optim 28:774–786MathSciNetCrossRef Miao Z, Wang Y, Xu L (2014) Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\)-colorable. J Comb Optim 28:774–786MathSciNetCrossRef
go back to reference Robertson N, Sanders D, Seymour P, Thomas R (1996) A new proof of the four color theorem. Electron Res Announc Am Math Soc 2:17–25CrossRef Robertson N, Sanders D, Seymour P, Thomas R (1996) A new proof of the four color theorem. Electron Res Announc Am Math Soc 2:17–25CrossRef
go back to reference Shehab M, Squincciarini A, Anh G, Kokkinoud I (2012) Access control for online social networks third party applications. Comput Secur 31:897–911CrossRef Shehab M, Squincciarini A, Anh G, Kokkinoud I (2012) Access control for online social networks third party applications. Comput Secur 31:897–911CrossRef
go back to reference Hill O, Smith D, Wang Y, Xu L, Yu G (2013) Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable. Discrete Math 313:2312–2317MathSciNetCrossRef Hill O, Smith D, Wang Y, Xu L, Yu G (2013) Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable. Discrete Math 313:2312–2317MathSciNetCrossRef
go back to reference Steinberg R (1993) The state of the three color problem. Quo vadis, graph theory? Ann Discrete Math 55:211–248CrossRef Steinberg R (1993) The state of the three color problem. Quo vadis, graph theory? Ann Discrete Math 55:211–248CrossRef
Metadata
Title
New restrictions on defective coloring with applications to steinberg-type graphs
Authors
Addie Armstrong
Nancy Eaton
Publication date
25-04-2020
Publisher
Springer US
Published in
Journal of Combinatorial Optimization / Issue 1/2020
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-020-00573-5

Other articles of this Issue 1/2020

Journal of Combinatorial Optimization 1/2020 Go to the issue

Premium Partner