zbMATH — the first resource for mathematics

The chromatic uniqueness of complete bipartite graphs. (English) Zbl 0752.05031
In the first part of this paper the author looks for the graph in a given class which has the maximum number of induced complete bipartite subgraphs. For graphs with a fixed number of vertices this maximum is achieved by the complete bipartite graph \(K_{n,n}\) or by \(K_{n,n+1}\). For graphs with a fixed number of edges the maximum is achieved by \(K_{1,n}\). The author determines a similar maximum for graphs with a given number of edges and a given maximum degree.
In the second part of the paper the author uses a result from the first half to prove that \(K_{n,m}\) is chromatically unique when \(n,m\geq 2\), i.e., that no other graph has the same chromatic polynomial as \(K_{n,m}\).

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Beineke, L.W.; Harary, F., The maximum number of strongly subtournamints, Canad. math. bull., 8, 491-498, (1965) · Zbl 0132.21303
[2] Bollabás, B., Extremal graph theory, (1978), Academic Press London
[3] Bollobás, B.; Nara, C.; Tachibana, S., The maximal number of induced complete bipartite graphs, Discrete math., 62, 271-275, (1986) · Zbl 0613.05028
[4] Chao, C.Y.; Novacky, G.A., On maximally saturated graphs, Discrete math., 41, 139-143, (1982) · Zbl 0495.05023
[5] Erdös, P., On the number of complete subgraphs contained in certain graphs, Publ. math. inst. hungar. acad. sci., I, 459-464, (1962) · Zbl 0116.01202
[6] Moon, J.W.; Moser, L., On cliques in graphs, Israel J. math., 3, 23-28, (1965) · Zbl 0144.23205
[7] Salzberg, P.M.; López, M.A.; Giudici, R.E., On the chromatic uniqueness of bipartite graphs, Discrete math., 58, 286-294, (1986) · Zbl 0594.05034
[8] Whitehead, E.G.; Zhao, L.C., Cutpoints and the chromatic polynomial, J. graph theory, 4, 371-377, (1984) · Zbl 0551.05041
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.