Chromaticity of the complements of paths and cycles. (English) Zbl 0870.05024
Summary: Let \(P_n\) and \(C_n\) denote the path and cycle of order \(n\). Z. Y. Guo and Y. J. Li conjectured that if \(G\) is a 2-regular graph without subgraph isomorphic to \(C_4\), then the complement of \(G\) is chromatically unique. We present a proof of this conjecture. We also obtain that if \(n_i\) is even and \(n_i\not\equiv 4\bmod 10\), then the complement of \(\bigcup^k_{i=1} P_{n_i}\) is chromatically unique. A new parameter \(\pi(G)\) of graph \(G\) and some recursive formulas are introduced as tools, and connected graphs with \(\pi(G)=0\) or 1 are characterized. The chromatic uniqueness of certain kinds of graphs is also discussed.
References:
| [1] | J.A. Bondy and U.S.R. Murty, Graph Theory with Application (North-Holland, Elsevier, New York).; J.A. Bondy and U.S.R. Murty, Graph Theory with Application (North-Holland, Elsevier, New York). · Zbl 1134.05001 |
| [2] | Chao, C. Y.; Novackay, G. A., On maximally saturated graphs, Discrete Math., 41, 139-143 (1982) · Zbl 0495.05023 |
| [3] | Dhurandhar, M., Characterization of quadratic and cube σ-polynomials, J. Combin. Theory Ser. B, 37, 210-220 (1984) · Zbl 0554.05030 |
| [4] | Du, Q., On σ-polynomials and a class of chromatically unique graphs, Discrete Math., 115, 153-165 (1993) · Zbl 0774.05039 |
| [5] | Farrell, E. J.; Whitehead, E. G., On matching and chromatic properties of circulants, J. Combin. Math. Combin. Comput., 79-88 (1990) · Zbl 0747.05068 |
| [6] | Guo, Z. Y.; Li, Y. J., Chromatic uniqueness of complement of the cycles union, ((1989), J. Wuhan Urban Construction Institute), 1-9, (Chinese, English summary) |
| [7] | Korfhage, R. R., σ-polynomials and graph colouring, J. Combin. Theory Ser. B, 24, 137-153 (1978) · Zbl 0845.05043 |
| [8] | Liu, R. Y.; Bao, X. G., Chromatic Uniqueness of the complements of 2-regular graphs, J. Pure Math. Appl. Math., 9, 69-71 (1993), (Chinese, English summary) |
| [9] | Read, R. C., An introduction to chromatic polynomials, J. Combin. Theory Ser. B, 4, 52-71 (1968) · Zbl 0173.26203 |
| [10] | Turan, P., On the theory of graphs, Colloq. Math., 3, 19-30 (1954) · Zbl 0055.17004 |
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.
