Clique chromatic numbers of intersection graphs

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\).

Recommendations

Cites work

Cited in

(22)

This page was built for publication: Clique chromatic numbers of intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2313617)