{
  "id": "1708.02264",
  "version": "v1",
  "published": "2017-08-07T18:50:27.000Z",
  "updated": "2017-08-07T18:50:27.000Z",
  "title": "On the clique number of the square of a line graph and its relation to Ore-degree",
  "authors": [
    "Maxime Faron",
    "Luke Postle"
  ],
  "comment": "11 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "In 1985, Erd\\H{o}s and Ne\\v{s}et\\v{r}il conjectured that the square of the line graph of a graph $G$, that is $L(G)^2$, can be colored with $\\frac{5}{4}\\Delta(G)^2$ colors. This conjecture implies the weaker conjecture that the clique number of such a graph, that is $\\omega(L(G)^2)$, is at most $\\frac{5}{4}\\Delta(G)^2$. In 2015, \\'Sleszy\\'nska-Nowak proved that $\\omega(L(G)^2)\\le \\frac{3}{2}\\Delta(G)^2$. In this paper, we prove that $\\omega(L(G)^2)\\le \\frac{4}{3}\\Delta(G)^2$. This theorem follows from our stronger result that $\\omega(L(G)^2)\\le \\frac{\\sigma(G)^2}{3}$ where $\\sigma(G) := \\max_{uv\\in E(G)} d(u) + d(v)$, is the Ore-degree of the graph $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-08-07T18:50:27.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "line graph",
      "clique number",
      "ore-degree",
      "stronger result",
      "conjecture implies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}