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 $ein 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 $ein 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 $ein 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 $nge k+2$ vertices, then [e(G)ge {k over 2}left(n- leftlceil {k over 2} rightrceil - varepsilonright) + {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 leftlceil {3k /2} rightrceil +2$.
Download