2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

For an upperbound, the clique number of a $k$-critical graph is obviously at most $k$, and this is achieved by the complete graph $K_k$. There is no non-trivial lowerbound for the clique number, and for good reason. Using Toft's graph, one can apply the Mycielski construction to obtain triangle-free $k$-critical graphs for all $k \geq 4$. A different and (optimally dense) construction of triangle-free $k$-critical graphs was obtained by Pegden.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thank you for your answer. Maybe I should be more precise. While we discuss the maximum number of edges in a $k$-critical graph, the number of vertices of this graph should always be fixed, denoted by $n$. When $n=k$, it is trivial. As you said, $K_k$ would be what we want. But when $n$ is strictly larger than $k$, it would be hard. Do you have any idea about the clique number of critical graphs in this case? $\endgroup$
    – CCC
    Commented Sep 19, 2023 at 16:18
  • 2
    $\begingroup$ @CCC Please edit the question you have posed to make it more clear. For example, you could start with asking for bounds on $\omega$ of an $n$-vertex $k$-critical graph, and then you can give all the definitions and history. It also helps to highlight your main question with the formatting tools. $\endgroup$
    – domotorp
    Commented Sep 20, 2023 at 7:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .