zbMATH — the first resource for mathematics

The chromaticity of complete bipartite graphs with at most one edge deleted. (English) Zbl 0712.05027
The chromatic polynomial of a graph G is denoted by P(G,\(\lambda\)). Two graphs are chromatically equivalent if they have the same chromatic polynomials. A graph G is said to be chromatically unique if every graph H with \(P(G,\lambda)=P(H,\lambda)\) is isomorphic with G.
The paper concerns with the characterization of chromatically unique graphs. All complete bipartitie graphs K(p,q), \(2\leq p\leq q,\) are chromatically unique. All graphs obtained from a complete bipartite graph K(p,q) by deleting one edge, where \(3\leq p\leq q\), are also chromatically unique. These results prove a conjecture of Salzberg, López, and Giudici.
Open questions concern the chromaticity of \(K(p,q)-\{e_ 1,e_ 2\}\) with \(4\leq p\leq q\) \((e_ 1,e_ 2\) are two distinct edges) and of \(K(p,q)+e\) with \(2\leq p\leq q\) (e is a new edge joining two vertices in a partite set).
Reviewer: U.Baumann

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Chao, Discrete Math. 41 pp 139– (1982)
[2] and , On chromatic equivalence of graphs. Lecture Notes in Mathematics, 642, Springer-Verlag, New York (1978) 121–131.
[3] Chao, Discrete Math. 27 pp 171– (1979)
[4] Chia, J. Graph Theory 10 pp 541– (1986)
[5] Farrell, Discrete Math. 29 pp 257– (1980)
[6] Giudici, Lecture Notes Pure Appl. Math. 96 pp 147– (1985)
[7] and , Two classes of chromatically unique graphs. Discrete Math., to appear. · Zbl 0697.05027
[8] Li, Ars Combinat. 23 pp 13– (1987)
[9] Loerinc, Discrete Math. 23 pp 313– (1978) · Zbl 0389.05034 · doi:10.1016/0012-365X(78)90012-2
[10] Read, J. Combinat. Theory 4 pp 52– (1968)
[11] Read, Ars Combinat. 23 pp 209– (1987)
[12] and , Chromatic polynomials. Selected Topics in Graph Theory 3, Academic Press, Orlandor, FL (1988) 15–42.
[13] Salzberg, Discrete Math. 58 pp 285– (1986)
[14] Tomescu, J. Graph Theory 11 pp 327– (1987)
[15] Whitehead, J. Graph Theory 8 pp 371– (1984)
[16] Zeros of chromatic polynomials. Combinatorial Surveys: Proceedings of the Sixth British Combinatorial Conference. Academic Press, London (1977) 199–223.
[17] 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.