A graph is totally critical if it is Type 2, connected, and the removal of any edge reduces the total chromatic number. A good characterization of all totally critical graphs is unlikely as Sanchez-Arroyo showed that determining the total chromatic number of a graph is an NP-hard problem. In this paper we show that if the Conformability Conjecture is correct, then totally critical graphs of even order with maximum degree at least one half of 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. We also show that if the maximum degree #DELTA# of a non-conformable graph G of even order satisfies 1/2|V| <= #DELTA# <= 3/4|V| -1 then G is regular and has a simple structure.
展开▼
机译:如果图形是2类,则该图形是非常关键的,并且删除任何边都会减少总色数。由于桑切斯·阿罗约(Sanchez-Arroyo)表明确定图的总色数是NP难题,因此不可能对所有完全关键的图进行良好的表征。在本文中,我们表明,如果一致性猜想是正确的,则偶数阶的最大临界图的最大程度至少为其阶的一半,可以通过一个简单的方程式来表征,该方程包括该阶次,最大程度,图的不足和补码的边缘独立性数。我们还表明,如果偶数阶不合格图G的最大程度#DELTA#满足1/2 | V |。 <=#DELTA#<= 3/4 | V | -1则G是规则的并且具有简单的结构。
展开▼