Fill This Form To Receive Instant Help

Help in Homework
trustpilot ratings
google ratings


Homework answers / question archive / What bound is given for X(G) by the theorem "for every graph G, X(G)<=1+max &(G') ,where the maximum is taken over all induced subgraphs G' of G" in the case that G is a) a tree? b) an outerplanar graph

What bound is given for X(G) by the theorem "for every graph G, X(G)<=1+max &(G') ,where the maximum is taken over all induced subgraphs G' of G" in the case that G is a) a tree? b) an outerplanar graph

Math

What bound is given for X(G) by the theorem "for every graph G,
X(G)<=1+max &(G') ,where the maximum is taken over all induced subgraphs G' of G" in the case that G is
a) a tree?
b) an outerplanar graph.

Note: -&(G') this sign represent the minimum degree of G'. Yes it is that minimum
-A graph G is outerplanar if it can be embedded in the plane so that every vertex of G lies on the boundary of the exterior region. A graph G is outerplanar if and only if G=K1 is planar.A graph G is outerplanar if and only if it contains no subgraphs that is a subdivision of either k4 or k2,3.
A graph G is outerplanar of order n>=2 and size m, then m<=2n-3.
Page 145 of the book Graph and Digraph" 4ed be G Chartrand and...
What does outerplanar graph?
draw a graph please.

pur-new-sol

Purchase A New Answer

Custom new solution created by our subject matter experts

GET A QUOTE

Answer Preview

What bound is given for X(G) by the theorem"for every graph G,
X(G)<=1+max &(G') ,where the maximum is taken over all induced subgraphs G' of G" in the case that G is
a) a tree?

Since any induced subgraph G' of a tree is a tree or a forest, we know that the minimum degree of G' is therefore 1. Hence,

So, the upper bound is 2, implying we can colour any tree by two colours.

b) an outerplanar graph.

Use a result you mentioned below in (*), we know that , where m is the number of edges and n is the number of vertices of an outerplanar graph G. As the sum of the degrees over all vertices in a graph G is twice the number of edges, namely

So,
.

We know that

Hence,

So,

Hence,

In other words, the minimum degree of every outplanar graph is at most 3.

By (**), we can know that any induced subgraph of an outplanar graph G is also an outplanar graph.

Hence, .

So, by a theorem, we have that

So, the upper bound is 4, implying we can colour any outplanar graphs by FOUR colours.

Note: represents the minimun degree of G'.

-A graph G is outerplanar if it can be embedded in the plane so that every vertex of G lies on the boundary of the exterior region.

A graph G is outerplanar if and only if G+K1 is planar. ....................(**)

A graph G is outerplanar if and only if it contains no subgraphs that is a subdivision of either k4 or k2,3.

A graph G is outerplanar of order n>=2 and size m, then m<=2n-3. ......(*)

Page 145 of the book Graph and Digraph" 4ed be G Chartrand and ..

What does outerplanar graph?
draw a graph please.

Here is an example of outerplanar graphs.

You can see every vertex is on the boundary (red cycle) of the exterior region.