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.8369282
0 references
0.8267715
0 references
0.8224343
0 references
0.81280893
0 references
0 references
0 references
0.79672337
0 references
0.7764813
0 references
0.7748591
0 references
0.7742487
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