
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.
vertex-coloring, edge independence number, Coloring of graphs and hypergraphs, total chromatic number, conformability, Computational Theory and Mathematics, maximum degree, Discrete Mathematics and Combinatorics, Structural characterization of families of graphs, deficiency, Theoretical Computer Science
vertex-coloring, edge independence number, Coloring of graphs and hypergraphs, total chromatic number, conformability, Computational Theory and Mathematics, maximum degree, Discrete Mathematics and Combinatorics, Structural characterization of families of graphs, deficiency, Theoretical Computer Science
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
