Chromatic uniqueness in a family of 2-connected graphs (Q1356689): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Hian Poh Yap / rank | |||
Property / reviewed by | |||
Property / reviewed by: Hian Poh Yap / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Chromatically unique graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The search for chromatically unique graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parallel concepts in graph theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An introduction to chromatic polynomials / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 14:12, 27 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Chromatic uniqueness in a family of 2-connected graphs |
scientific article |
Statements
Chromatic uniqueness in a family of 2-connected graphs (English)
0 references
14 January 1998
0 references
Let \(P(G,\lambda)\) be the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are said to be chromatically equivalent if \(P(G,\lambda)= P(H,\lambda)\). A graph \(G\) is said to be chromatically unique, if there exists no graph \(H\), which is not isomorphic with \(G\), but \(G\) and \(H\) are chromatically equivalent. For integers \(n\geq 4\) and \(k\geq 1\), the graph \(F_{n,k}\) is defined as follows. Let \(H_n= P_{n-1}+ K_1\) be the join of a path \(P_{n-1}\) on \(n-1\) vertices with a vertex. Then \(H_n\) has exactly two vertices, say \(x\) and \(y\), each of degree 2. The graph \(F_{n,k}\) is obtained from \(H_n\) by adjoining \(k\) new vertices \(u_1,u_2,\dots,u_k\) and adding \(2k\) edges joining them to \(x\) and \(y\). The author proves that, for any odd integer \(n\geq 5\) and any integer \(k\geq 1\), \(F_{n,k}\) is chromatically unique. This gives a partial solution to Problem 5 given in \textit{K. M. Koh} and \textit{K. L. Teo} [The search for chromatically unique graphs, Graphs Comb. 6, No. 3, 259-285 (1990; Zbl 0727.05023)]. Reviewer's remark: K. L. Teo was misprinted as C. P. Teo in this paper.
0 references
chromatic polynomial
0 references
chromatically equivalent
0 references
chromatically unique
0 references