## On 4-critical t-perfect graphs

*Benchetrit, Yohann*;

- Subject: Mathematics - Combinatorics | Computer Science - Discrete Mathematics

- References (28)
[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 No metrics available

- Download from

- Cite this publication