Theorem 2.1 For every graph G, o (G) ≤ x (G). Proof It suffices to assume that G is a nontrivial connected graph. Suppose that x (G) = k and A(G) = A, and let d = A + 1. Let c' be a proper k-coloring of G, using the colors 1, 2, ..., k. So adjacent vertices of G are colored differently by c'. Define a k-coloring c of G by c(v) = di-1 if c'(v) = i. We show that c is a sigma coloring of G, which implies that o (G) ≤ k = x (G). Let u and u be two adjacent vertices of G, where c'(u) =s and c'(v) = t. Then st. Let S be the multiset of colors assigned by c' to the neighbors of u and let T be the multiset of colors assigned by c' to the neighbors of v. Since s E T-S and t€ S-T, it follows that S T. Hence there is a largest integer j with max{s, t} ≤ j≤ k such that S and T contain j an unequal number of times. Suppose that S contains j a total of a times and T contains j a total of b times, where say 0 ≤a
Theorem 2.1 For every graph G, o (G) ≤ x (G). Proof It suffices to assume that G is a nontrivial connected graph. Suppose that x (G) = k and A(G) = A, and let d = A + 1. Let c' be a proper k-coloring of G, using the colors 1, 2, ..., k. So adjacent vertices of G are colored differently by c'. Define a k-coloring c of G by c(v) = di-1 if c'(v) = i. We show that c is a sigma coloring of G, which implies that o (G) ≤ k = x (G). Let u and u be two adjacent vertices of G, where c'(u) =s and c'(v) = t. Then st. Let S be the multiset of colors assigned by c' to the neighbors of u and let T be the multiset of colors assigned by c' to the neighbors of v. Since s E T-S and t€ S-T, it follows that S T. Hence there is a largest integer j with max{s, t} ≤ j≤ k such that S and T contain j an unequal number of times. Suppose that S contains j a total of a times and T contains j a total of b times, where say 0 ≤a
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
Illustrate the proof
Transcribed Image Text:Theorem 2.1 For every graph G, o (G) ≤ x (G).
Proof It suffices to assume that G is a nontrivial connected graph. Suppose that
x (G) = k and A(G) = A, and let d = A + 1. Let c' be a proper k-coloring of
G, using the colors 1, 2, ..., k. So adjacent vertices of G are colored differently by
c'. Define a k-coloring c of G by
c(v) = di- if c'(v) = i.
We show that c is a sigma coloring of G, which implies that o (G) ≤ k = x (G).
Let u and u be two adjacent vertices of G, where c'(u) =s and c'(v) = t. Then
st. Let S be the multiset of colors assigned by c' to the neighbors of u and let T be the
multiset of colors assigned by c' to the neighbors of v. Since se T-S and t€ S-T,
it follows that S T. Hence there is a largest integer j with max(s, t) ≤ j≤ k such
that S and T contain j an unequal number of times. Suppose that S contains j a total
of a times and T contains j a total of b times, where say 0 ≤a <b≤A.
We claim that o (u) o (v) for the coloring c. Let
r=
while
k-j-1
Σadk-1-i,
i=0
where ao, a1,..., ak-j-1 are nonnegative integers. From the defining property of j,
it follows that
o(u) = r + adj-¹ + p₁ (d) and o(v) = r + bd³-¹ + p2(d),
where pi(d) and p2 (d) are polynomials in d having degree at most j - 2. Thus
o(u) = r + adj-¹ + p₁(d) ≤r + adj-¹ + Adj-2
<r+adi-¹ +di-¹ = r + (a + 1)d¹-¹ ≤r+bdj-¹,
(2)
o (v) = r + bdj−¹ + p2(d) ≥ r + bdj−¹.
Thus o (u) < o (v) and so c is a sigma coloring of G.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps with 23 images
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
