publication . Preprint . 2016

On 4-critical t-perfect graphs

Benchetrit, Yohann;
Open Access English
  • Published: 08 Apr 2016
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 of the prism $\Pi$ (a graph is 4-critical if it has chromatic number 4 and all its proper induced subgraphs are 3-colorable). In this paper, we show a new example of a 4-critical $t$-perfect graph: the complement of the line graph of the 5-wheel $W_5$. Furthermore, we prove that these two examples are in fact the only 4-critical $t$-perfect graphs in the class of complements of line graphs. As a by...
free text keywords: Computer Science - Discrete Mathematics, Mathematics - Combinatorics
Related Organizations
Download from
28 references, page 1 of 2

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

[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

[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. [OpenAIRE]

[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. [OpenAIRE]

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

[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.

[11] D.R Fulkerson. Anti-blocking polyhedra. Journal of Combinatorial Theory, Series B, 12(1):50 - 71, 1972. [OpenAIRE]

[12] A.M.H. Gerards and B. Shepherd. The graphs with all subgraphs t-perfect. SIAM J. Discrete Math., 11(4):524-545, 1998.

[13] M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization. Algorithms and combinatorics. Springer-Verlag, Berlin, New York, 1988. [OpenAIRE]

[14] L. Lovász. Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics, 2(3):253 - 267, 1972. [OpenAIRE]

[15] L. Lovász. A note on factor-critical graphs. Studia Sci. Math. Hungar., 7:279- 280, 1972.

28 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue