Example of graph with specific $\chi (G)$, $\omega (G)$, $\beta (G)$

1,796

I'm not sure if it's right but here is an example for G:

Example here

χ(G) = 3,
ω(G) = 2,
β(G) = 3 and
θ(G) = 3

Share:
1,796

Related videos on Youtube

user2553807
Author by

user2553807

Updated on February 27, 2020

Comments

  • user2553807
    user2553807 over 3 years

    Find an original example of a graph whose chromatic number does not equal its clique number, yet whose clique partition number equals its independence number.

    Chromatic number: $\chi(G)$ is the minimum colors needed to color a graph

    Clique number: $\omega (G)$ is the maximum number of vertices of a complete subgraph of the graph

    Independence number: $\beta (G)$ is the largest set of independent vertices

    Clique partition: least number of cliques that partition the vertex set

    *I know what each component means and how to find it but I can't find an example that fits all of the pieces of criteria. Right now I am just trying random graphs- is there a systematic ways to do this?

    • hardmath
      hardmath over 7 years
      I notice that there is no requirement that the graph be connected, so it might be helpful to consider using a component (such as a pentagon) that gives a chromatic number higher than its clique number, then fix up the equality of clique partition number and independence number with additional components.
  • Shailesh
    Shailesh over 7 years
    Since the graph is simple enough you could also describe it right in the answer.
  • Ali
    Ali over 7 years
    Edition done. Now the picture is right in the answer.