Totally critical even order graphs (Q1306315): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Q3941433 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3832589 / rank
 
Normal rank
Property / cites work
 
Property / cites work: 1-factorizing regular graphs of high degree - an improved bound / rank
 
Normal rank
Property / cites work
 
Property / cites work: Total colorings of graphs of order \(2n\) having maximum degree \(2n-2\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5342984 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5620621 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A total-chromatic number analogue of Plantholt's theorem / rank
 
Normal rank
Property / cites work
 
Property / cites work: The total chromatic number of graphs having large maximum degree / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4351068 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4386302 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree / rank
 
Normal rank
Property / cites work
 
Property / cites work: Determining the total colouring number is NP-hard / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5564127 / rank
 
Normal rank

Latest revision as of 08:28, 29 May 2024

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
    total chromatic number
    0 references
    maximum degree
    0 references
    deficiency
    0 references
    vertex-coloring
    0 references
    conformability
    0 references
    edge independence number
    0 references

    Identifiers