Example of graph with specific $\chi (G)$, $\omega (G)$, $\beta (G)$
I'm not sure if it's right but here is an example for G:
χ(G) = 3,
ω(G) = 2,
β(G) = 3 and
θ(G) = 3
Related videos on Youtube
user2553807
Updated on February 27, 2020Comments
-
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 over 7 yearsI 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 over 7 yearsSince the graph is simple enough you could also describe it right in the answer.
-
Ali over 7 yearsEdition done. Now the picture is right in the answer.