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

Gang Chen, Zhengke Miao, Zi-Xia Song, Jingmei Zhang

Published 2021-09-01Version 1

A well-known theorem of Vizing states that if $G$ is a simple graph with maximum degree $\Delta$, then the chromatic index $\chi'(G)$ of $G$ is $\Delta$ or $\Delta+1$. A graph $G$ is class 1 if $\chi'(G)=\Delta$, and class 2 if $\chi'(G)=\Delta+1$; $G$ is $\Delta$-critical if it is connected, class 2 and $\chi'(G-e)<\chi'(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'(G+e)=\chi'(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 $\varepsilon$ 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 \left\lceil {3k /2} \right\rceil +2$.