Description: Definitions from Galvin/Komj\'ath [1991] for forms [1 AT] through [1 AW].

Content:

Definitions from Galvin/Komj\'ath [1991] for forms [1 AT] through [1 AW].

Definition: Assume that \(G=(V,E)\) is a graph.

  1. \(S\subseteq V\) is dependent if \(\{x,y\} \in S\) for some \(\{x,y\} \in E\).  Otherwise \(S\) is independent.
  2. \(f: V\to C\) is a good coloring if \(f^{-1}(c)\) is independent for each \(c\in C\).
  3. Let \(\kappa = |C|\), then \(G\) is \(\kappa\) colorable if there is a good coloring \(f: V\to C\).  (\(C\) need not be well orderable.)
  4. The least \(\kappa\) for which \(G\) is \(\kappa \) colorable (if it exists) is the chromatic number of \(G\).
  5. A good coloring \(f:G\to C\) is irreducible if \(f^{-1}(c_1) \cup f^{-1}(c_2)\) is dependent whenever \(c_1,c_2 \in C\) and \(c_1\ne c_2\). (So a graph admits an irreducible good coloring just in case its vertex set can be partitioned into independent sets such that the union of any two is dependent.)
  6. For any two sets \(A\) and \(B\) define the graph \(G(A,B)\) with vertex set \(A\times B\) by \((a_1,b_1) \ne (a_2,b_2) \) are adjacent if \(a_1 = a_2\) or \(b_1 = b_2\).

Howard-Rubin number: 118

Type: Definitions

Back