An upper bound for the total chromatic number (Q2277479): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
ReferenceBot (talk | contribs)
Changed an Item
 
(4 intermediate revisions by 3 users not shown)
Property / reviewed by
 
Property / reviewed by: John Mitchem / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: John Mitchem / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Colour Numbers of Complete Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Nombre Chromatique Total Du Graphe <i>R</i> -Parti Complet / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3996285 / rank
 
Normal rank
Property / cites work
 
Property / cites work: List-colourings of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The total coloring of a multigraph with maximal degree 4 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the total coloring of certain graphs / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 15:15, 21 June 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
    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
    0 references

    Identifiers