[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

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

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  • Appel K, Haken W (1977) Every planar map is four colorable. Illinois J Math Parts I II 21:429–567

    Article  MathSciNet  Google Scholar 

  • Bopche G, Mehtrea M (2017) Graph similarity metrics for assessing temporal changes in attack surface of dynamic networks. Comput Secur 64:16–43

    Article  Google Scholar 

  • 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–311

    Article  MathSciNet  Google Scholar 

  • 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–456

    Article  MathSciNet  Google Scholar 

  • Cowen LJ, Cowen RH, Woodall DR (1986) Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. J Gr Theory 10:187–195

    Article  MathSciNet  Google Scholar 

  • 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–905

    Article  MathSciNet  Google Scholar 

  • Grünbaum B (1964) Grötzsch theorem on 3-colorings. Michigan Math J 10:303–310

    MATH  Google Scholar 

  • Jensen T, Toft B (1995) Gr Color Probl. Wiley, New York

    Google Scholar 

  • 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–786

    Article  MathSciNet  Google Scholar 

  • 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–25

    Article  Google Scholar 

  • Shehab M, Squincciarini A, Anh G, Kokkinoud I (2012) Access control for online social networks third party applications. Comput Secur 31:897–911

    Article  Google Scholar 

  • 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–2317

    Article  MathSciNet  Google Scholar 

  • Steinberg R (1993) The state of the three color problem. Quo vadis, graph theory? Ann Discrete Math 55:211–248

    Article  Google Scholar 

Download references

Acknowledgements

We are grateful to our institutions, Norwich University and the University of Rhode Island, for supporting this research. The work was made possible, in part, by a Norwich University Chase Research Release award for the first author. We would also like to thank the anonymous referees for their helpful suggestions in clarifying parts of the paper.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Addie Armstrong.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Armstrong, A., Eaton, N. New restrictions on defective coloring with applications to steinberg-type graphs. J Comb Optim 40, 181–204 (2020). https://doi.org/10.1007/s10878-020-00573-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-020-00573-5

Keywords

Navigation