An upper bound for the total chromatic number (Q2277479): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 11:18, 2 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An upper bound for the total chromatic number |
scientific article |
Statements
An upper bound for the total chromatic number (English)
0 references
1990
0 references
The chromatic number, the edge chromatic number, and the total chromatic number of a graph H are respectively denoted by \(\chi\) (H), \(\chi '(H)\), and \(\chi ''(H)\). Theorem: For any graph H, \(\chi ''(H)\leq \chi '(H)+2\lceil \sqrt{\chi (H)}\rceil.\) Let \(\Delta\) (H) be the maximum degree of graph H. The proof of the theorem relies on the following interesting lemma: Let \(H=(V,E)\) be a graph with \(\chi '(H)=\Delta (H)\) and W be an independent subset of V. Any coloring of W with \(\Delta\) (H) colors can be extended to a proper coloring of \(W\cup E\) with \(\Delta (H)+1\) colors such that if edge e is colored with the new color, then one of the vertices incident with e is in W.
0 references
edge chromatic number
0 references
total chromatic number
0 references