ON UNIQUELY -G k-COLOURABLE GRAPHS (Q4034558)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 167621
Language Label Description Also known as
default for all languages
No label defined
    English
    ON UNIQUELY -G k-COLOURABLE GRAPHS
    scientific article; zbMATH DE number 167621

      Statements

      ON UNIQUELY -G k-COLOURABLE GRAPHS (English)
      0 references
      16 May 1993
      0 references
      generalized coloring
      0 references
      forbidden monochromatic subgraph
      0 references
      clique number
      0 references
      0 references
      0 references
      Given a graph \(G\), a graph \(F\) is \(-G\) \(k\)-colorable if its vertices can be colored with \(k\) colors so that no subgraph \(F\) induced by the subset of vertices of any single color is isomorphic to \(G\). If \(G=K_ 2\), we retrieve the standard definition of proper coloring. If \(F\) is \(-G\) \(k\)- colorable but not \(-G (k-1)\)-colorable then \(F\) is \(-G\) \(k\)-chromatic, and if, in addition, \(F\) has a unique \(-G\) \(k\)-coloring, up to a permutation of colors, then \(F\) is uniquely \(-G\) \(k\)-colorable. In [J. Graph Theory 11, 87-99 (1987; Zbl 0608.05035)] the authors showed that if \(G\) is any graph with at least 3 vertices such that either \(G\) or its complement has a vertex adjacent to all the others, then for any \(k\geq 2\) there are infinitely man uniquely \(-G\) \(k\)-colorable graphs. In the paper under review it is shown that if \(G\) is any graph with at least 3 vertices such that either \(G\) or its complement is 2-connected, then for any \(k\geq 2\) there are infinitely many uniquely \(-G\) \(k\)-colorable graphs with the same clique number as \(G\).
      0 references

      Identifiers