Skip to main content
MathOverflow

Return to Question

added 2 characters in body
Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17

An independent set is a set of vertices in a graph, no two of which are adjacent. A maximum independent set is an independent set of the largest possible size for a given graph. The size of a maximum independent set is called the independence numberindependence number of $G$ and is usually denoted by $α(G)$.

It is easy to see that $α(G)=1$ if and only if $G$ is a complete graph. So if $α(G)=2$, is there also a characterizationcharacterization? And go on, for $α(G)=3$...

If there is no characterization, are there any necessary or sufficient conditions? For example, it appears that these graphs are not too sparse. Is there a lower bound on the number of their edges?

An independent set is a set of vertices in a graph, no two of which are adjacent. A maximum independent set is an independent set of the largest possible size for a given graph. The size of a maximum independent set is called the independence number of $G$ and is usually denoted by $α(G)$.

It is easy to see that $α(G)=1$ if and only if $G$ is a complete graph. So if $α(G)=2$, is there also a characterization? And go on, for $α(G)=3$...

If there is no characterization, are there any necessary or sufficient conditions?

An independent set is a set of vertices in a graph, no two of which are adjacent. A maximum independent set is an independent set of the largest possible size for a given graph. The size of a maximum independent set is called the independence number of $G$ and is usually denoted by $α(G)$.

It is easy to see that $α(G)=1$ if and only if $G$ is a complete graph. So if $α(G)=2$, is there also a characterization? And go on, for $α(G)=3$...

If there is no characterization, are there any necessary or sufficient conditions? For example, it appears that these graphs are not too sparse. Is there a lower bound on the number of their edges?

added 86 characters in body
Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17

An independent set is a set of vertices in a graph, no two of which are adjacent. A maximum independent set is an independent set of the largest possible size for a given graph. The size of a maximum independent set is called the independence number of $G$ and is usually denoted by $α(G)$.

It is easy to see that $α(G)=1$ if and only if $G$ is a complete graph. So if $α(G)=2$, is there also a characterization? And go on, for $α(G)=3$...

If there is no characterization, are there any necessary or sufficient conditions?

An independent set is a set of vertices in a graph, no two of which are adjacent. A maximum independent set is an independent set of the largest possible size for a given graph. The size of a maximum independent set is called the independence number of $G$ and is usually denoted by $α(G)$.

It is easy to see that $α(G)=1$ if and only if $G$ is a complete graph. So if $α(G)=2$, is there also a characterization? And go on, for $α(G)=3$...

An independent set is a set of vertices in a graph, no two of which are adjacent. A maximum independent set is an independent set of the largest possible size for a given graph. The size of a maximum independent set is called the independence number of $G$ and is usually denoted by $α(G)$.

It is easy to see that $α(G)=1$ if and only if $G$ is a complete graph. So if $α(G)=2$, is there also a characterization? And go on, for $α(G)=3$...

If there is no characterization, are there any necessary or sufficient conditions?

Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17

Is there a characterization for graphs with independence number two?

An independent set is a set of vertices in a graph, no two of which are adjacent. A maximum independent set is an independent set of the largest possible size for a given graph. The size of a maximum independent set is called the independence number of $G$ and is usually denoted by $α(G)$.

It is easy to see that $α(G)=1$ if and only if $G$ is a complete graph. So if $α(G)=2$, is there also a characterization? And go on, for $α(G)=3$...