On the size of special class 1 graphs and $(P_3;k)$-co-critical graphs

Abstract

A well-known theorem of Vizing states that if $G$ is a simple graph with maximum degree $\Delta$, then the chromatic index ${\chi }^{\prime }(G)$ of $G$ is $\Delta$ or $\Delta +1$. A graph $G$ is class 1 if ${\chi }^{\prime }(G)=\Delta$, and class 2 if ${\chi }^{\prime }(G)=\Delta +1$; $G$ is $\Delta$-critical if it is connected, class 2 and ${\chi }^{\prime }(G-e)<{\chi }^{\prime }(G)$ for every $e\in E(G)$. A long-standing conjecture of Vizing from 1968 states that every $\Delta$-critical graph on $n$ vertices has at least $(n(\Delta -1)+3)/2$ edges. We initiate the study of determining the minimum number of edges of class 1 graphs $G$, in addition, ${\chi }^{\prime }(G+e)={\chi }^{\prime }(G)+1$ for every $e\in E(\overline{G})$. Such graphs have intimate relation to $(P_3;k)$-co-critical graphs, where a non-complete graph $G$ is $(P_3;k)$-co-critical if there exists a $k$-coloring of $E(G)$ such that $G$ does not contain a monochromatic copy of $P_3$ but every $k$-coloring of $E(G+e)$ contains a monochromatic copy of $P_3$ for every $e\in E(\overline{G})$. We use the bound on the size of the aforementioned class 1 graphs to study the minimum number of edges over all $(P_3;k)$-co-critical graphs. We prove that if $G$ is a $(P_3;k)$-co-critical graph on $n\ge k+2$ vertices, then \[e(G)\ge {k \over 2}\left(n- \left\lceil {k \over 2} \right\rceil - \varepsilon\right) + {\lceil k/2 \rceil+\varepsilon \choose 2},\] where $\epsilon$ is the remainder of $n-\lceil k/2\rceil$ when divided by $2$. This bound is best possible for all $k\ge 1$ and $n\ge \lceil 3k/2\rceil +2$.

To appear in Discrete Mathematics. arXiv admin note: text overlap with arXiv:2104.13898