zbMATH — the first resource for mathematics

On 3-colorings of partite p-threshold graphs. (English) Zbl 0662.05024
Let P(G,\(\lambda)\) denote the chromatic polynomial of a graph G. Two graphs G and H are chromatically equivalent if \(P(G,\lambda)=P(H,\lambda)\). G is chromatically unique if it is chromatically equivalent to no other graph. The author defines a bipartite p-threshold graph which is a generalization of a threshold graph. Loosely speaking, in a bipartite p-threshold graph any two vertices which are not comparable belong to different partite sets. He examines properties of 3-colorings of complete bipartite graphs which are extremely in the class of all bipartite p-threshold graphs that are uniquely 2-colorable. As a consequence it is shown that the complete bipartite graphs \(K_{p,p+r}\) are chromatically unique if \(p\geq 2\) and \(0\leq r<2\sqrt{p+1}\).
Reviewer: D.S.Archdeacon

05C15 Coloring of graphs and hypergraphs
05C99 Graph theory
Full Text: DOI
[1] Chao, Discrete Math. 41 pp 139– (1982)
[2] and , On chromatic equivalence of graphs. In Theory and Applications of Graphs. Lecture Notes in Math. Vol. 642. Springer-Verlag, Berlin (1978) 121–131.
[3] Chao, Discrete Math. 27 pp 171– (1979)
[4] Chvátal, Ann. Discrete Math. 1 pp 145– (1977)
[5] Giudici, Discrete Math. 58 pp 285– (1986)
[6] Peled, J. Graph Theory 8 pp 331– (1984)
[7] Read, J. Combinatorial Theory 4 pp 52– (1968) · Zbl 0165.32802
[8] Problems in Combinatorics and Graph Theory. J. Wiley, New York (1985).
[9] Turán, Colloq. Math. 3 pp 19– (1954)
[10] Whitehead, J. Graph Theory 8 pp 355– (1984)
[11] Whitehead, J. Graph Theory 8 pp 371– (1984)
[12] Xu, Discrete Math. 51 pp 207– (1984)
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.