On \(q\)-graphs (Q1366792)

From MaRDI portal





scientific article
Language Label Description Also known as
English
On \(q\)-graphs
scientific article

    Statements

    On \(q\)-graphs (English)
    0 references
    0 references
    0 references
    0 references
    22 January 1998
    0 references
    The smallest \(q\)-tree is the complete graph on \(q\) vertices and a \(q\)-tree with \(n+1\) vertices, \(n\geq q\), is obtained by adding a new vertex adjacent to \(q\) mutually adjacent vertices of a \(q\)-tree on \(n\) vertices. A graph is a \(q\)-graph if it contains a \(q\)-tree as a spanning subgraph. In the paper it is proved that if \(G\) is a \(q\)-graph, \(|V(G)|>q\), then the multiplicity of the root \(q\) of the chromatic polynomial equals the number of \(q\)-blocks. Moreover, a characterization of chromatically unique graphs is given.
    0 references
    chromatic polynomial
    0 references
    chromatically unique graph
    0 references
    \(q\)-graph
    0 references
    \(q\)-tree
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers