Graph Coloring - Kent State University

Graph Coloring - Kent State University

Presented By Ravindra Babu, Pentyala Real World Problem What is Coloring Planar Graphs Vertex Coloring Edge Coloring

NP Hard Problem Problem Explanation Assigning of a GSM frequencies in INDIA such that no two states frequencies could not be overlapped. How can we assign the frequencies such that least number of frequencies can be used.

This is applicable to all the countries. Graph Coloring is an assignment of colors (or any distinct marks) to the vertices of a graph. Strictly speaking, a coloring is a proper coloring if no two

adjacent vertices have the same color. f : V (G ) S Definition: A graph is planar if it can be drawn in a plane without edge-crossings.

The four color theorem: For every planar graph, the chromatic number is 4. Was posed as a conjecture in the 1850s. Finally proved in 1976(Appel and Haken) by the aid of computers.

The four color theorem states that any planar map can be colored with at most four colors. In graph terminology, this means that using at most four colors, any planar graph can have its nodes colored such that no two adjacent nodes have the same color. Four-color conjecture Francis Guthrie, 1852 (F.G.)

Many incomplete proofs (Kempe). 5-color theorem proved in 1890 (Heawood) 4-color theorem finally proved in 1977 (Appel, Haken) First major computer-based proof A vertex coloring is an assignment of labels or colors

to each vertex of a graph such that no edge connects two identically colored vertices Similar to vertex coloring, except edges are color. Adjacent edges have different colors. Every edge-coloring problem can be transformed into a

vertex-coloring problem Coloring the edges of graph G is the same as coloring the vertices in L(G) Not every vertex-coloring problem can be transformed to an edge-coloring problem Every graph has a line graph, but not every graph is a line graph of some other graph

K-Coloring A k-coloring of a graph G is a mapping of V(G) onto the integers 1..k such that adjacent vertices map into different integers. A k-coloring partitions V(G) into k disjoint subsets

such that vertices from different subsets have different colors. K-colorable A graph G is k-colorable if it has a k-coloring.

Chromatic Number The smallest integer k for which G is k-colorable is called the chromatic number of G, is denoted by the (G). NP: the class of decision problems that are solvable in

polynomial time on a nondeterministic machine (or with a nondeterministic algorithm) (A deterministic computer is what we know) A nondeterministic computer is one that can guess the right answer or solution think of a nondeterministic computer as a parallel machine that can freely spawn an infinite number of processes Thus NP can also be thought of as the class of problems

whose solutions can be verified in polynomial time Note that NP stands for Nondeterministic Polynomial-time Fractional Knapsack Sorting Others? Graph Coloring Satisfiability (SAT)

the problem of deciding whether a given Boolean formula is satisfiable. Many problems can be formulated as a graph coloring problem including Time Tabling, Scheduling, Register Allocation, Channel Assignment. A lot of research has been done in this area so much is

already known about the problem space. The standard approach to coloring a map is to use a single color for a state and never use the same color for two states. Two states whose common border is just one point can be colored, if we so choose, with the same color.

GSM networks operate in only four different frequency ranges. The reason why only four different frequencies because any country can colored with four different colors.

aph_Coloring_in_Modern_Computer_Science M/GSM_chap3.pdf Thank You Questions. ?

Recently Viewed Presentations

  • Combating Aids & Famine Across Africa  2014 Brain

    Combating Aids & Famine Across Africa 2014 Brain

    Standards. SS7CG3 . The student will analyze how politics in Africa impacts standard of living. b. Describe the impact of government stability on the distribution of resources to combat AIDS and famine across Africa.
  • Ground Rules, exams, etc. (no "make up" exams) Text: read ...

    Ground Rules, exams, etc. (no "make up" exams) Text: read ...

    Similar resources favor specialists, different resources favor generalists MacArthur "Economics of Consumer Choice" Robust theorem: Diets contract when prey abundant MacArthur and Levins limiting similarity model Ambush versus Active Foragers: optimal foraging Compression Hypothesis Fisher's model of adaptation and deterioration...
  • Seeing 3D from 2D Images - University of Florida

    Seeing 3D from 2D Images - University of Florida

    Seeing 3D from 2D Images Ghosting Affected by the amount of light transmitted by the LC shutter in its off state. Phosphor persistence Vertical screen position of the image. Time-parallel stereoscopic images Image quality may also be affected by Right...
  • FAITH & REASON and the decisions we make…

    FAITH & REASON and the decisions we make…

    PROPORTIONALISM Has to do with comparing or balancing the good and evil effects that an action causes in a given situation in relation to the end pursued. Everything depends upon the proportion established between the consequences of an act. INTRINSICALLY...
  • Wellbeing Presenter name, position, trust Date Acknowledgements We

    Wellbeing Presenter name, position, trust Date Acknowledgements We

    perspective - Possessing positive psychological functioning, good relationships with others and self-realisation. This includes the capacity for self-development, positive relations with others, autonomy, self-acceptance and competence.
  • Chapter 18 Classification

    Chapter 18 Classification

    DKPCOFGS copyright cmassengale * * Hierarchy-Taxonomic Groups Domain Kingdom Phylum (Division - used for plants) Class Order Family Genus Species BROADEST TAXON Most Specific copyright cmassengale * Dumb King Phillip Came Over For Gooseberry Soup! copyright cmassengale * copyright cmassengale...
  • The First Americans

    The First Americans

    * What is the title of this map? 2. What 2 Historical Circumstances led the humans to first migrate into the Americas? TTQA Migrated from the cold climate to the warm climate Followed the food source of animals across the...
  • Soteriology - Amazon S3

    Soteriology - Amazon S3

    "Repentance is a supernatural and inward revelation from God, giving a deep consciousness of what I am in His sight, which causes me to loathe and condemn myself, resulting in a bitter sorrow for sin, a holy horror and hatred...