Nonexistence of certain 4-critical graphs of order 12 (Q919008)

The well-known Vizing theorem [\textit{V. G. Vizing}, Diskretn. Analiz. 3, 25-30 (1964)], states that chromatic index \(\chi '(G)\) of a simple graph G with maximum vertex degree \(\rho\) is equal either to \(\rho\) or to \(\rho +1\). A connected graph G with maximum degree \(\rho\) is said to be \(\rho\)- critical if \(\chi '(G)=\rho +1\) and elimination of any edge lowers its chromatic number. The important question of the existence of critical graphs with a given even number of nodes remains unsolved. A partial solution has been provided. Here we consider graphs of order 12 with maximum degree 4 and prove following Theorem: There are no 4-critical graphs with partition \(2^ 44^ 8\).