{
  "id": "2412.19230",
  "version": "v1",
  "published": "2024-12-26T14:16:15.000Z",
  "updated": "2024-12-26T14:16:15.000Z",
  "title": "Semistrong edge colorings of planar graphs",
  "authors": [
    "Yuquan Lin",
    "Wensong Lin"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Strengthened notions of a matching $M$ of a graph $G$ have been considered, requiring that the matching $M$ has some properties with respect to the subgraph $G_M$ of $G$ induced by the vertices covered by $M$: If $M$ is the unique perfect matching of $G_M$, then $M$ is a uniquely restricted matching of $G$; if all the edges of $M$ are pendant edges of $G_M$, then $M$ is a semistrong matching of $G$; if all the vertices of $G_M$ are pendant, then $M$ is an induced matching of $G$. Strengthened notions of edge coloring and of the chromatic index follow. In this paper, we consider the maximum semistrong chromatic index of planar graphs with given maximum degree $\\Delta$. We prove that graphs with maximum average degree less than ${14}/{5}$ have semistrong chromatic index (hence uniquely restricted chromatic index) at most $2\\Delta+4$, and we reduce the bound to $2\\Delta+2$ if the maximum average degree is less than ${8}/{3}$. These cases cover, in particular, the cases of planar graphs with girth at least 7 (resp. at least 8). Our result makes some progress on the conjecture of Lu\\v{z}ar, Mockov\\v{c}iakov\\'a and Sot\\'ak [J. Graph Theory 105 (2024) 612--632], which asserts that every planar graph $G$ has a semistrong edge coloring with $2\\Delta+C$ colors, for some universal constant $C$. (Note that such a conjecture would fail for strong edge coloring as there exist graphs with arbitrarily large maximum degree that are not strongly $(4\\Delta-5)$-edge-colorable.) We conjecture that the upper bound for both the uniquely restricted chromatic index and the semistrong chromatic index of planar graphs with maximum degree $\\Delta$ is $2\\Delta+4$, and provide an example of a planar graph achieving this bound.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-12-26T14:16:15.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "planar graph",
      "semistrong edge coloring",
      "uniquely restricted chromatic index",
      "maximum average degree",
      "maximum degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}