Largest to a smallest colour class

Assignment Help Science
Reference no: EM13937628

Given a graph G and a proper vertex r-colouring c : V(G) ! [r], we can draw an auxiliary directed graph Ac on vertex set [r] by putting, for each i 6= j, an arc !i j if there is a vertex in c1(i) which has no neighbours in c1(j) (in other words, if there is a vertex with colour i which we could recolour to j and still have a proper colouring).
An equitable r-colouring of G is a proper vertex r-colouring c : V(G) ! [r] such that
c1(i)
=
c1(j)
1 for each i, j 2 [r] (in other words, any two colour classes differ in size by at most
one).
Suppose from now on that D(G)  k, for some integer k  1, and that c is a proper vertex r-colouring of G such that 1 
c1(1)
    
c1(r)
.
(a) What is the minimum number of arcs in Ac leaving each i? (Your answer should not depend on G or i, but only on r and k, and you must both give an example (G, c, i) showing that you can have so few arcs leaving i, and also a proof that for any G, c and i
you cannot have fewer)

(b) What is the minimum number of arcs entering 1? How does the answer change if in addition you are told that
!
n1 is not in Ac, and
c1(n)
>
c1(1)
? In both cases, give
both a lower bound on the minimum number and also an example showing it is best possible.
(c) Suppose that r  2k. Prove that there is a directed path in Ac from a largest to a smallest colour class. Deduce that G has an equitable r-colouring.
(d) Give a polynomial-time algorithm which, on input a graph G with maximum degree k and any r  2k, returns an equitable r-colouring. Prove your algorithm is correct and has polynomial running time.
(e) (Bonus Points) Prove that if k  2 then G also has an equitable (2k  1)-colouring.

The distance square G(2) of G is the graph on V(G) with xy 2 E

G(2)
if either xy 2 E(G) or
x 6= y and xz and yz are in E(G) for some z 2 V(G) (In other words, xy is in E
G(2)
if x and
y are at distance one or two from each other in G).
(f) If D(G)  k, how large can D
G(2)
be? Give an upper bound and an example which shows it is best possible. If c is a proper vertex r-colouring of G(2), then what structure

does c reveal in G? (In other words, what can we say about the edges of G within one, or between two, colour classes of c?) Given two graphs G and H, we say f is an embedding of G into H if f : V(G) ! V(H) is injective (so f(x) 6= f(y) whenever x 6= y), and for all edges xy of G, the pair f(x)f(y) is an edge of H. (Note that this is not an ‘if and only if' condition, so if xy is not an edge of G then f(x)f(y) may or may not be an edge of H). If there exists an embedding of G into H, we say H contains G. MA408 | Discrete Mathematics and Graph Theory Assessed Coursework | Page 3

Suppose that G has 2k2n vertices (we assume V(G) is disjoint from [2k2n]), and c is an equitable (2k2)-colouring of G(2). Consider the following algorithm, which for input (G, c, p), where p 2 [0, 1] may depend on n, returns a graph H on 2k2n vertices and either an embedding f of G into H or ‘Fail'.
Algorithm 1: Embed(G, c, p)
Let V(H) = [2k2n] ;
Let f1 : c1(1) ! V(H) be an arbitrary injective map with image f1, . . . , ng ;
For each unordered pair x, y in f1, . . . , ng, independently, add xy to H with probability
p ;
foreach i = 2, . . . , 2k2 do
For each unordered pair x, y with x 2 [in] and y 2 f(i  1)n + 1, . . . , ing, independently, add xy to H with probability p ;
if fi1 6= ‘Fail' then
Let V(Fi) = c1(i) [ f(i 1)n + 1, . . . , ing ;
foreach u 2 c1(i) and x 2 f(i 1)n + 1, . . . , ing do
If fi1(v)x is an edge of H for each neighbour v of u with c(v) < i, add ux to Fi ;
end
if Fi has a perfect matching then
Let M be a perfect matching in Fi ;
Define fi : c1(f1, . . . , ig) ! V(H) by fi(u) = fi1(u) if c(u) < i and
fi(u) = x if c(u) = i and ux 2 M ;
end
else

Reference no: EM13937628

Questions Cloud

What is the par value of the companys common stock : What is the par value of the company's common stock? Did the company issue any new shares during the fiscal year ended December 31, 2006?
The general journal entry to record this transaction : On September 1, Ziegler Corporation had 71,000 shares of $5 par value common stock, and $213,000 of retained earnings. On that date, when the market price of the stock is $15 per share, the corporation issues a 2-for-1 stock split. The general journa..
What is estimate of intrinsic value per share : The Generic Genetic (GG) Corporation pays no cash dividends currently and is not expected to for the next 4 years. Its latest EPS was $5.2, all of which was reinvested in the company. The firm’s expected ROE for the next 4 years is 18% per year, duri..
Calculates the total ticket sales after each game : The first line indicates that the ticket price is $250 and that 5750 tickets were sold at that price. Output the number of tickets sold and the total sale amount. Format your output with two deciamal places.
Largest to a smallest colour class : Given a graph G and a proper vertex r-colouring c : V(G) ! [r], we can draw an auxiliary directed graph Ac on vertex set [r] by putting, for each i 6= j, an arc !i j if there is a vertex in c1(i) which has no neighbours in c1(j) (in other words, i..
Write a c code to find the sum of n natural numbers : Write a C++ code to find the sum of n natural numbers up to given term.
Telecommunications from university of south australia : Have recently completed my masters in telecommunications from university of south Australia and i want to assess my bachelors degree(electronics) with engineers Australia" student wants it to be assesed in electronics as he wants his bachelors de..
Essay on the topic brazilian students : Elaborate the essay on the topic Brazilian students and U S Culture Shock into 5 or 6 pages and reorganize the ideas.
Equipment required will cost-depreciated on straight-line : McGilla Golf has decided to sell a new line of golf clubs. The length of this project is seven years. The company has spent $1125482 on research and development for the new clubs. The plant and equipment required will cost $28303428 and will be depre..

Reviews

Write a Review

Science Questions & Answers

  Implications of emotional intelligence for leaders

What are the implications of emotional intelligence for leaders? Explain your answer by using personal examples. A key component of leadership is:

  The defendant criminal history

The defendant's criminal history

  Work breakdown structure and network diagram

According to the PMBOK Guide, "the WBS is a deliverable-oriented hierarchical decomposition of the work to be executed by the project team, to accomplish the project objectives and create the required deliverables." In other words, it lists the pr..

  An anxiety disorder

Jake has become very anxious ever since he started taking harder classes in his major. The university's counselor diagnosed him with an anxiety disorder.

  Autonomy impact an individual"s ability issues

Explore how polices and legislation could impact the faimly and individual  during each life cycle.

  How does a managers personality and values affect his or

1.what factors do you think influence employee job satisfaction? compare and contrast these factors to the factors

  Compare and contrast two models of conceptualizing addiction

Compare and contrast two models of conceptualizing addiction

  Describes your understanding of grice rules of conversation

Describes your understanding of Grice rules of conversation

  Explain how this might affect society

Imagine the U.S. as a nation that did not practice any types of religion. Explain how this might affect society.

  Bureaucracy''s rule making powers is least accurate

Which of the following statements about the federal bureaucracy's rule making powers is LEAST accurate? Select one:a. Bureaucratic agencies are often tasked with drafting specific rules to meet general guidelines established by Congress.b. The public..

  Teva in innovative pharmaceutical and biosimilars.

Analyze the opportunites for Teva in innovative pharmaceutical and biosimilars.

  What are the common causative factors

What are the common causative factors? What does data indicate? What are the effective proven corrective measures?

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd