{
  "id": "2109.00466",
  "version": "v1",
  "published": "2021-09-01T16:16:10.000Z",
  "updated": "2021-09-01T16:16:10.000Z",
  "title": "On the size of special class 1 graphs and $(P_3; k)$-co-critical graphs",
  "authors": [
    "Gang Chen",
    "Zhengke Miao",
    "Zi-Xia Song",
    "Jingmei Zhang"
  ],
  "comment": "To appear in Discrete Mathematics. arXiv admin note: text overlap with arXiv:2104.13898",
  "categories": [
    "math.CO"
  ],
  "abstract": "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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-09-01T16:16:10.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "co-critical graph",
      "special class",
      "monochromatic copy",
      "minimum number",
      "simple graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}