On the chromatic uniqueness of certain bipartite graphs (Q1182976): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Yee-Hock Peng / rank | |||
Property / reviewed by | |||
Property / reviewed by: Dan S. Archdeacon / rank | |||
Property / author | |||
Property / author: Yee-Hock Peng / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Dan S. Archdeacon / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4187840 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Chromatically unique graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On chromatic equivalence of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The chromaticity of wheels with a missing spoke / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On chromatic coefficients / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3320409 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3682504 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Two classes of chromatically unique graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4032988 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An introduction to chromatic polynomials / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3819084 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the chromatic uniqueness of bipartite graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The chromaticity of complete bipartite graphs with at most one edge deleted / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On 3-colorings of bipartitep-threshold graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cutpoints and the chromatic polynomial / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4128619 / rank | |||
Normal rank |
Latest revision as of 15:35, 15 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the chromatic uniqueness of certain bipartite graphs |
scientific article |
Statements
On the chromatic uniqueness of certain bipartite graphs (English)
0 references
28 June 1992
0 references
A graph \(G\) is chromatically unique if any other graph with the same chromatic polynomial is isomorphic to \(G\). For example, it is known that the complete bipartite graph \(K(n,m)\) is chromatically unique provided \(n,m\geq 2\), as is the complete graph minus a single edge \(K^{-1}(n,m)\) provided \(n,m\geq 3\). In this paper the author extends the investigation into the chromatic uniqueness of complete bipartite graphs minus 2, 3, or 4 edges. Let \(K^{-r}(n,m)\) denote the class of complete bipartite graphs \(K(n,m)\) with \(r\) edges removed. There are 3 graphs in \(K^{-r}(n,m)\) when \(r=2\), 6 graphs when \(r=3\), and 16 graphs for \(r=4\). The author derives a sufficient condition for a graph in \(K^{-2}(n,m)\) to be chromatically unique. In particular, each such graph is chromatically unique when \(| n-m|\leq 3\). Moreover, graphs with \(| n-m|=d\) are chromatically unique provided that \(n\) is sufficiently large (an explicit polynomial bound is given). In the class \(K^{-3}(m,m)\) any member is chromatically unique provided \(| n-m|\leq 1\) (with a few small exceptions). In \(K^{-4}(n,m)\) any graph is chromatically unique provided \(n=m\geq 4\). Also, each graph in \(K^{-4}(n,n+1)\) is chromatically unique for \(n\geq 5\). A few other results of a similar nature are presented.
0 references
chromatic uniqueness
0 references
chromatic polynomial
0 references