The existence of uniquely -G colourable graphs

DOI10.1016/S0012-365X(97)00022-8MaRDI QIDQ1377702zbMATH OpenFDO

Authors D. Achlioptas, Jason I. Brown, Derek G. Corneil, Michael Molloy

Publication date 24 March 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(97)00022-8

zbMATH Keywords

\(k\)-colourable graph hypergraph uniquely colourable graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Review text

Given graphs \(F\) and \(G\) and a nonnegative integer \(k\), a function \(\pi :V(F)\rightarrow \{1,\ldots ,k\}\) is a \(-G\) \(k\)-colouring of \(F\) if no induced copy of \(G\) is monochromatic; \(F\) is \(-G\) \(k\)-chromatic if \(F\) has a \(-G\) \(k\)-colouring but no \(-G\) \((k-1)\)-colouring. Further, we say \(F\) is uniquely \(-G\) \(k\)-colourable if \(G\) is \(-G\) \(k\)-chromatic and, up to a permutation of colours, it has only one \(-G\) \(k\)-colouring. It was conjectured by \textit{J. I. Brown} and \textit{D. G. Corneil} [J. Graph Theory 11, 87-99 (1987; Zbl 0608.05035)] that uniquely \(-G\) \(k\)-colourable graphs exist for all graphs \(G\) of order at least 2 and all positive integers \(k\). What has been known so far is that the conjecture holds whenever \(G\) or its complement has a universal vertex or is 2-connected. In this paper the conjecture is completely settled by showing that, in fact, in all cases infinitely many such graphs exist.

Recommendations

Cites work

Cited in

(18)

This page was built for publication: The existence of uniquely \(-G\) colourable graphs

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