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.
- \(S\subseteq V\) is dependent if \(\{x,y\} \in S\) for some
\(\{x,y\} \in E\). Otherwise \(S\) is independent.
- \(f: V\to C\) is a good coloring if \(f^{-1}(c)\) is
independent for each \(c\in C\).
- Let \(\kappa = |C|\), then \(G\) is \(\kappa\) colorable if
there is a good coloring \(f: V\to C\). (\(C\) need not be well orderable.)
- The least \(\kappa\) for which \(G\) is \(\kappa \) colorable (if
it exists) is the chromatic number of \(G\).
- 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.)
- 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