Document Type
Lecture
Publication Date
1-31-2014
Abstract
Given an undirected graph G, the chromatic number χ(G) is the minimum number of partitions of V(G) into independent sets. Given a directed graph D, a vertex set is acyclic if it does not contain a directed cycle. The chromatic number χ(D) is the minimum number of partitions of V(D) into acyclic sets. The dichromatic number of an undirected graph G, denoted χ→(G), is the maximum chromatic number over all its orientations. Erdős and Neumann-Lara proved that C₁·n/log n ≤ χ→(Kₙ) ≤ C₂·n/log n for some constants C₁, C₂. They conjectured that if the dichromatic number of a graph is bounded, so is its chromatic number. Let ��(G) be the set of all independent sets of G, and ��(G, x) be the subset containing x. For each I ∈ ��(G), assign a variable x_I ≥ 0. The fractional chromatic number χ_f(G) is the minimum of Σ x_I over I ∈ ��(G), subject to Σ x_I ≥ 1 for each vertex x ∈ V(G). We prove there is a constant C such that for any graph G, χ→(Kₙ) ≤ C·n/log n. This is joint work with Professor Bojan Mohar.
Relational Format
presentation
Recommended Citation
Wu, Hehui, "Dicromatic number and fractional chromatic number" (2014). Colloquium. 33.
https://egrove.olemiss.edu/math_colloquium/33
