Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Graphs and Their Applications Read chapter Read first chapter

2017 | OriginalPaper | Chapter

7. Graph Coloring

Author : Md. Saidur Rahman

Published in: Basic Graph Theory

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Probably graph coloring concept naturally arose from its application in map coloring: given a map containing several countries, we wish to color the countries in the map in such a way that neighboring countries receive different colors to make the countries distinct. In this chapter we know about vertex coloring, edge coloring, chromatic number, chromatic index, chromatic polynomial, etc.

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!

inform now

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!

inform now

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!

inform now
previous chapter Planar Graphs
next chapter Digraphs
Appendix
Available only for authorised users
Literature
1.
Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H. Freeman and Company, New York (1979)
2.
Matula, D.W., Marble, G., Isaacson, J.D.: Graph colouring algorithms. In: Read, R.C. (ed.) Graph Theory and Computing, pp. 109–122. Academic Press, New York (1972)CrossRef
3.
Welsh, D.J.A., Powell, M.B.: An upper bound for chromatic number of a graph and its application to timetabling problem. Comput. J. 10, 85–86 (1967)CrossRefMATH
4.
5.
Matula, D.W., Schiloach, Y., Tarjan, R.E.: Two linear algorithms for five coloring of planar graphs. STAN-CS-80-830 (1980)
6.
7.
Appel, K., Haken, W.: Every map is four colourable. Bull. Am. Math. Soc. 82, 711–712 (1976)
8.
9.
Vizing, V.G.: On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3, 25–30 (1964)
10.
11.
12.
Agnarsson, G., Greenlaw, R.: Graph Theory: Modeling, Applications and Algorithms. Pearson Education Inc., New Jersey (2007)
13.
Gebremedhin, A.H., Tarafdar, A., Manne, F., Pothen, A.: New acyclic and star coloring algorithms with application to computing hessians. SIAM J. Sci. Comput. 29(3), 1042–1072 (2007)MathSciNetCrossRefMATH
14.
Gebremedhin, A.H., Tarafdar, A., Pothen, A., Walther, A.: Efficient computation of sparse hessians using coloring and automatic differentiation. INFORMS J. Comput. 21(2), 209–223 (2009)MathSciNetCrossRefMATH
15.
16.
17.
18.
Ochem, P.: Negative results on acyclic improper colorings. In: Proceedings of European Conference on Combinatorics (EuroComb 05), pp. 357–362 (2005)
19.
Mondal, D., Nishat, R.I., Whitesides, S., Rahman, M.S.: Acyclic colorings of graph subdivisions revisited. J. Discret. Algorithms 16, 90–103 (2012)MathSciNetCrossRefMATH
20.
Wilson, R.J.: Introduction to Graph Theory, 4th edn. Longman, London (1996)MATH
Metadata
Title
Graph Coloring
Author
Md. Saidur Rahman
Copyright Year
2017
Book
Basic Graph Theory

Print ISBN: 978-3-319-49474-6

Electronic ISBN: 978-3-319-49475-3

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-49475-3_7

Premium Partner

    Image Credits