×

A class of edge critical 4-chromatic graphs. (English) Zbl 0881.05044

Edge critical 4-chromatic graphs with some additional properties (e.g. arbitrary large girth) are constructed by adding a number of (in some cases just three) independent edges to a bipartite graph.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abbott, HL; Hare, DR; Zhou, B., Sparse color-critical graphs and hypergraphs with no short cycles, 18 · Zbl 0805.05059
[2] Descartes, B.: Solution to advanced problem No. 4526. American Mathematical Monthly 61, 352 (1954) · doi:10.2307/2307489
[3] Bondy, J.A., Murty, U.S.: Graph theory with applications. New York: American Elsevier Publishing 1976 · Zbl 1226.05083
[4] Erdős, P.: Problems and results in graph theory and combinatorial analysis. In Problémes Combinatoires et Théorie des Graphes, Colloques Internationaux du C.N.R.S. No. 260, 127-129 (Orsay, 1976)
[5] Erdős, P.; Faudree, RJ; Rousseau, CC; Schelp, RH, On cycle-complete graph Ramsey numbers, 2 · Zbl 0383.05027
[6] Erdős, P.; Hajnal, A., On chromatic number of graphs and set systems, 17 · Zbl 0151.33701
[7] Gallai, T.: Kritische Graphen (2), Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 8, 165-192 (1963) · Zbl 0121.18401
[8] Lovász, L., On chromatic number of finite set systems, 19 · Zbl 0157.55203
[9] Nielsen, F.; Toft, B., On a class of planar 4-chromatic graphs due to T. Gallai, 425-430 (1975), Praha
[10] Nešetřil, J., Rödl, V.: A short proof for the existence of highly chromatic hypergraphs without short cycles. J. of Comb. Theory Ser. B 27, 225-227 (1979) · Zbl 0413.05039
[11] Toft, B.: On the maximal number of edges of k-chromatic graphs. Studia Sci. Math. Hung. 5, 461-470 (1970) · Zbl 0228.05111
[12] Rödl, V., Tuza, Zs.: On Color Critical Graphs. J. Comb. Theory Ser. B 38, 204-213 (1985) · Zbl 0566.05030 · doi:10.1016/0095-8956(85)90066-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.