×

The Hadwiger number, chordal graphs and \(ab\)-perfection. (English) Zbl 1372.05082

Summary: A graph is chordal if every induced cycle has three vertices. The Hadwiger number is the order of the largest complete minor of a graph. We characterize the chordal graphs in terms of the Hadwiger number and we also characterize the families of graphs such that for each induced subgraph \(H\), (1) the Hadwiger number of \(H\) is equal to the maximum clique order of \(H\), (2) the Hadwiger number of \(H\) is equal to the achromatic number of \(H\), (3) the \(b\)-chromatic number is equal to the pseudoachromatic number, (4) the pseudo-\(b\)-chromatic number is equal to the pseudoachromatic number, (5) the Hadwiger number of \(H\) is equal to the Grundy number of \(H\), and (6) the \(b\)-chromatic number is equal to the pseudo-Grundy number.

MSC:

05C15 Coloring of graphs and hypergraphs
05C83 Graph minors
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abrams, L.; Berman, Y., Connected pseudoachromatic index of complete graphs, Australas. J. Combin., 60, 314-324 (2014) · Zbl 1305.05065
[2] Hadwiger, H., Ungelöste probleme 26, Elem. Math., 13, 128-129 (1958)
[3] Berge, C., Färbung von Graphen, deren sämtliche bzw. ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Natur. Reih, 10, 114 (1961)
[4] Christen, C. A.; Selkow, S. M., Some perfect coloring properties of graphs, J. Combin. Theory Ser. B, 27, 1, 49-59 (1979) · Zbl 0427.05033
[5] Araujo-Pardo, G.; Rubio-Montiel, C., The \(\omega \psi \)-perfection of graphs, Electron. Notes Discrete Math., 44, 163-168 (2013)
[6] Araujo-Pardo, G.; Rubio-Montiel, C., On \(\omega \psi \)-perfect graphs, Ars Combin. (2016), in press · Zbl 1440.05097
[7] Blidia, M.; Ikhlef Eschouf, N.; Maffray, F., Characterization of \(b \gamma \)-perfect graphs, AKCE Int. J. Graphs Comb., 9, 1, 21-29 (2012) · Zbl 1256.05067
[8] Rautenbach, D.; Zverovich, V. E., Perfect graphs of strong domination and independent strong domination, Discrete Math., 226, 1-3, 297-311 (2001) · Zbl 0972.05037
[9] Rubio-Montiel, C., A new characterization of trivially perfect graphs, Electron. J. Graph Theory Appl., 3, 1, 22-26 (2015) · Zbl 1467.05088
[10] Yegnanarayanan, V., Graph colourings and partitions, Theoret. Comput. Sci., 263, 1-2, 59-74 (2001) · Zbl 0979.68065
[11] Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2, 3, 253-267 (1972) · Zbl 0239.05111
[12] Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R., The strong perfect graph theorem, Ann. of Math., 164, 1, 51-229 (2006) · Zbl 1112.05042
[13] Hajnal, A.; Surányi, J., Über die Auflösung von Graphen in vollständige Teilgraphen, Ann. Univ. Sci. Budapest. Eötvös. Sect. Math., 1, 113-121 (1958) · Zbl 0093.37801
[14] Dirac, G. A., On rigid circuit graphs, Abh. Math. Semin. Univ. Hambg., 25, 71-76 (1961) · Zbl 0098.14703
[15] Chartrand, G.; Zhang, P., Chromatic graph theory, (Discrete Mathematics and its Applications, (Boca Raton) (2009), CRC Press: CRC Press Boca Raton, FL) · Zbl 1169.05001
[16] Gupta, R. P., Bounds on the chromatic and achromatic numbers of complementary graphs., (Recent Progress in Combinatorics. Recent Progress in Combinatorics, Proc. Third Waterloo Conf. on Comb., 1968 (1969), Academic Press: Academic Press New York), 229-235
[17] Harary, F.; Hedetniemi, S.; Prins, G., An interpolation theorem for graphical homomorphisms, Port. Math., 26, 453-462 (1967) · Zbl 0187.20903
[18] Berge, C., Perfect graphs, (Studies in Graph Theory, Part I. Studies in Graph Theory, Part I, Studies in Math., vol. 11 (1975), Math. Assoc. Amer.: Math. Assoc. Amer. Washington, D. C.), 1-22
[19] Grundy, P. M., Mathematics and games, Eureka, 2, 6-8 (1939)
[20] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
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.