Skip to main content
edited tags
Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
To make this question more specified.
Source Link
CCC
  • 51
  • 2

A graph $G$ is called a ${\it{k}}$-${\it{critical}}$ graph if $\chi(G)=k$ and for any proper subgraph $H$ of $G$ we have $\chi(H)<k$, where $\chi(G)$ denotes the chromatic number of $G$. The structure of critical graphs attracts many researchers' attention.

The maximum number of edges in a $n$-vertex $k$-critical graph $f_k(n)$ is one of the related topics. When $n=k$, this is trivial since $K_k$ is a $k$-crititcal graph. Hence we consider the case in which $n>k$. When $k=4$, Toft gave a well-known construction called ${\it{Toft}}$ ${\it{graph}}$. In general cases, Cong Luo, Jie Ma, and Tianchi Yang showed a Toft-like local structure when $K_{k-2}$ exits in a $k$-critical graph. For details, I would refer you to the following DOI: https://doi.org/10.1017/S0963548323000238

Now here comes my question. It seems that the size of cliques in a critical graph plays a very important role in determining the number of edges in this graph, since in C-M-Y's generalization of Toft's construction the existence of $K_{k-2}$ is the key point. But as I searched by myself, I haven't found any research on the clique number of critical graphs yet. Is there any bound on the clique number of critical graphs known now? Is there any construction of critical graphs with a small clique number known now?Is there any bound on the clique number of critical graphs known now($n>k$)? Is there any construction of critical graphs with a small clique number known now?

A graph $G$ is called a ${\it{k}}$-${\it{critical}}$ graph if $\chi(G)=k$ and for any proper subgraph $H$ of $G$ we have $\chi(H)<k$, where $\chi(G)$ denotes the chromatic number of $G$. The structure of critical graphs attracts many researchers' attention.

The number of edges in a $n$-vertex $k$-critical graph is one of the related topics. When $k=4$, Toft gave a well-known construction called ${\it{Toft}}$ ${\it{graph}}$. In general cases, Cong Luo, Jie Ma, and Tianchi Yang showed a Toft-like local structure when $K_{k-2}$ exits in a $k$-critical graph. For details, I would refer you to the following DOI: https://doi.org/10.1017/S0963548323000238

Now here comes my question. It seems that the size of cliques in a critical graph plays a very important role in determining the number of edges in this graph, since in C-M-Y's generalization of Toft's construction the existence of $K_{k-2}$ is the key point. But as I searched by myself, I haven't found any research on the clique number of critical graphs yet. Is there any bound on the clique number of critical graphs known now? Is there any construction of critical graphs with a small clique number known now?

A graph $G$ is called a ${\it{k}}$-${\it{critical}}$ graph if $\chi(G)=k$ and for any proper subgraph $H$ of $G$ we have $\chi(H)<k$, where $\chi(G)$ denotes the chromatic number of $G$. The structure of critical graphs attracts many researchers' attention.

The maximum number of edges in a $n$-vertex $k$-critical graph $f_k(n)$ is one of the related topics. When $n=k$, this is trivial since $K_k$ is a $k$-crititcal graph. Hence we consider the case in which $n>k$. When $k=4$, Toft gave a well-known construction called ${\it{Toft}}$ ${\it{graph}}$. In general cases, Cong Luo, Jie Ma, and Tianchi Yang showed a Toft-like local structure when $K_{k-2}$ exits in a $k$-critical graph. For details, I would refer you to the following DOI: https://doi.org/10.1017/S0963548323000238

Now here comes my question. It seems that the size of cliques in a critical graph plays a very important role in determining the number of edges in this graph, since in C-M-Y's generalization of Toft's construction the existence of $K_{k-2}$ is the key point. But as I searched by myself, I haven't found any research on the clique number of critical graphs yet. Is there any bound on the clique number of critical graphs known now($n>k$)? Is there any construction of critical graphs with a small clique number known now?

Source Link
CCC
  • 51
  • 2

Clique number of $k$-critical graphs

A graph $G$ is called a ${\it{k}}$-${\it{critical}}$ graph if $\chi(G)=k$ and for any proper subgraph $H$ of $G$ we have $\chi(H)<k$, where $\chi(G)$ denotes the chromatic number of $G$. The structure of critical graphs attracts many researchers' attention.

The number of edges in a $n$-vertex $k$-critical graph is one of the related topics. When $k=4$, Toft gave a well-known construction called ${\it{Toft}}$ ${\it{graph}}$. In general cases, Cong Luo, Jie Ma, and Tianchi Yang showed a Toft-like local structure when $K_{k-2}$ exits in a $k$-critical graph. For details, I would refer you to the following DOI: https://doi.org/10.1017/S0963548323000238

Now here comes my question. It seems that the size of cliques in a critical graph plays a very important role in determining the number of edges in this graph, since in C-M-Y's generalization of Toft's construction the existence of $K_{k-2}$ is the key point. But as I searched by myself, I haven't found any research on the clique number of critical graphs yet. Is there any bound on the clique number of critical graphs known now? Is there any construction of critical graphs with a small clique number known now?