Totally critical even order graphs (Q1306315)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Totally critical even order graphs
scientific article

    Statements

    Totally critical even order graphs (English)
    0 references
    0 references
    0 references
    0 references
    20 December 1999
    0 references
    A connected graph \(G\) is totally critical if its total chromatic number is at least two more than its maximum degree and is reduced by the removal of an arbitrary edge. Let \(G(p,q)\) have maximum degree \(\Delta(G)\); the deficiency of \(G\) is given by \(\text{def}(G)= \Delta(G)p- 2q\). A vertex-coloring of \(G\) from color set \(\{1,2,\dots, \Delta+1\}\) is conformable if the number of color classes (including empty ones) whose parity differs from that of \(p\) is at most \(\text{def}(G)\); \(G\) is conformable if it has such a vertex-coloring. The conformability conjecture is: Let \(G\) satisfy \(\Delta(G)\geq (p+1)/2\); then \(G\) is totally critical if and only if \(G\) is non-conformable and has no non-conformable subgraphs of the same maximum degree, or \(\Delta(G)\) is even and \(G\) results from the complete graph of order \(\Delta(G)+1\) by subdividing one edge. The authors show that if this conjecture is true, then totally critical even-order graphs with maximum degree at least half their order are characterized by a simple equation involving the order, maximum degree, and deficiency of the graph and the edge independence number of the complement.
    0 references
    0 references
    total chromatic number
    0 references
    maximum degree
    0 references
    deficiency
    0 references
    vertex-coloring
    0 references
    conformability
    0 references
    edge independence number
    0 references
    0 references