Clique chromatic numbers of intersection graphs (Q2313617)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Clique chromatic numbers of intersection graphs |
scientific article |
Statements
Clique chromatic numbers of intersection graphs (English)
0 references
19 July 2019
0 references
The clique chromatic number \(\chi_c(G)\) of a graph \(G\) is the minimum \(k\) for which there exists a \(k\)-coloring of the vertices of \(G\) such that all inclusion-maximal cliques, except for isolated vertices, are non-monochromatic. When \([n]=\{1,2,\dots,n\}\), \(G(n,r,s)\) is the graph whose vertex-set is \(\binom{[n]}{r}\), and whose edges join pairs of sets whose intersection contains exactly \(s\) elements. Proposition 1. Let \(n\ge r(r+1)\); then \(\chi_c(G(n,r,0))=2\). Proposition 2. Let \(s\ne0\); then \(\chi_c(G(n,r,s))\to\infty\) as \(n\to\infty\). Further, if \(q=\chi_c(G(n,r,s))\), then \(n < R_r(s+(r-s)(r-s+1),q)\). Here, \(R_r(m,q)\) is the Ramsey number, i.e., the minimal \(N\) such that, for each \(q\)-coloring of the complete \(r\)-homogeneous hypergraph on \(N\) vertices, there exists a monochromatic complete subgraph on \(m\) vertices. Proposition 3. If \(n<R_r(r+1,q-r-1)\), then \(\chi_c(G(n,r,r-1))\le q\).
0 references
intersection graph
0 references
clique chromatic number
0 references