On 4-critical t-perfect graphs

Preprint English OPEN
Benchetrit, Yohann;
  • Subject: Mathematics - Combinatorics | Computer Science - Discrete Mathematics

It is an open question whether the chromatic number of $t$-perfect graphs is bounded by a constant. The largest known value for this parameter is 4, and the only example of a 4-critical $t$-perfect graph, due to Laurent and Seymour, is the complement of the line graph o... View more
  • References (28)
    28 references, page 1 of 3

    [1] L. W. Beineke. Characterizations of derived graphs. Journal of Combinatorial Theory, 9(2):129 - 135, 1970.

    [2] Y. Benchetrit and A. Sebo˝ . Ear-decompositions, the complexity of the matching polytope and h-perfect graphs. arXiv preprint arXiv:1509.05586, 2015.

    [3] Y. Benchetrit and A. Ulmer. The chromatic number of t-perfect nearly-bipartite graphs. In preparation.

    [4] G. Brinkmann, K. Coolsaet, J. Goedgebeur, and H. Mélot. House of graphs: a database of interesting graphs. Discrete Applied Mathematics, 2013. Available at https://hog.grinvin.org/data/critical/N3P6_vertexcritical_all_sorted.g6.

    [5] H. Bruhn and E. Fuchs. t-perfection in near-bipartite and in P5 -free graphs. arXiv preprint arXiv:1507.00173, 2015.

    [6] H. Bruhn and O. Schaudt. Claw-free t-perfect graphs can be recognised in polynomial time. In Jon Lee and Jens Vygen, editors, Integer Programming and Combinatorial Optimization, volume 8494 of Lecture Notes in Computer Science, pages 404-415. Springer International Publishing, 2014.

    [7] H. Bruhn and M. Stein. On claw-free t-perfect graphs. Math. Program., 133(1- 2):461-480, 2012.

    [8] M. Chudnovsky, J. Goedgebeur, O. Schaudt, and M. Zhong. Obstructions for three-coloring graphs without induced paths on six vertices. ArXiv e-prints, April 2015.

    [9] V. Chvátal. On certain polytopes associated with graphs. Journal of Combinatorial Theory, Series B, 18:138-154, 1975.

    [10] W.H. Cunningham and A.B. Marsh. A primal algorithm for optimum matching. In M.L. Balinski and A.J. Hoffman, editors, Polyhedral Combinatorics, volume 8 of Mathematical Programming Studies, pages 50-72. Springer Berlin Heidelberg, 1978.

  • Metrics
Share - Bookmark