{
  "id": "1210.7844",
  "version": "v5",
  "published": "2012-10-29T21:17:01.000Z",
  "updated": "2014-10-29T17:40:33.000Z",
  "title": "Unified spectral bounds on the chromatic number",
  "authors": [
    "Clive Elphick",
    "Pawel Wocjan"
  ],
  "categories": [
    "math.CO",
    "cs.DM",
    "quant-ph"
  ],
  "abstract": "One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to Alan Hoffman, where mu_1 and mu_n are respectively the maximum and minimum eigenvalues of the adjacency matrix: chi >= 1 + mu_1 / (- mu_n). We recently generalised this bound to include all eigenvalues of the adjacency matrix. In this paper, we further generalize these results to include all eigenvalues of the adjacency, Laplacian and signless Laplacian matrices. The various known bounds are also unified by considering the normalized adjacency matrix, and examples are cited for which the new bounds outperform known bounds.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2013-01-18T18:14:00.000Z",
      "title": "New spectral bounds on the chromatic number",
      "abstract": "One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to Alan Hoffman, where mu_1 and mu_n are respectively the maximum and minimum eigenvalues of the adjacency matrix: q >= 1 + mu_1 / -mu_n. Vladimir Nikiforov has proved an eigenvalue inequality for Hermitian matrices, which enabled him to derive the first hybrid lower bound for the chromatic number, which uses the maximum eigenvalues of the adjacency and Laplacian matrices. His bound equals the Hoffman bound for regular graphs and is sometimes better for irregular graphs. In this paper we use majorization to generalize Nikiforov's eigenvalue inequality, which leads to generalizations of the Hoffman, Nikiforov and two Kolotilina bounds. These new bounds use all eigenvalues of the adjacency, Laplacian and signless Laplacian matrices. We compare the performance of these bounds for named and random graphs, and provide examples of graphs for which the new bounds outperform known bounds. We also prove that q >= 1 + 1 / -mu_n^*, where mu_n^* is the smallest eigenvalue of the normalized adjacency matrix, and then generalize this bound to all eigenvalues. We demonstrate that this normalized bound performs better than the Hoffman and Kolotilina bounds for many irregular named graphs. Our proof relies on a technique of converting the adjacency matrix into the zero matrix by conjugating with q diagonal unitary matrices. We also prove that the minimum number of diagonal unitary matrices that can be used to convert the adjacency matrix into the zero matrix is the normalized orthogonal rank, which can be strictly less than the chromatic number.",
      "comment": "Added new results in Subsection 2.2 explaining connections to vector chromatic numbers",
      "journal": null,
      "doi": null
    },
    {
      "version": "v5",
      "updated": "2014-10-29T17:40:33.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "chromatic number",
      "adjacency matrix",
      "spectral bounds",
      "diagonal unitary matrices",
      "first hybrid lower bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1210.7844E"
    }
  }
}