Relaxed coloring of a graph (Q1393026)

From MaRDI portal
Revision as of 19:18, 10 December 2024 by Import241208061232 (talk | contribs) (Normalize DOI.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Relaxed coloring of a graph
scientific article

    Statements

    Relaxed coloring of a graph (English)
    0 references
    0 references
    0 references
    18 July 1999
    0 references
    For a family \(\mathcal H\) of graphs, the \(\mathcal H\)-restricted chromatic number of \(G\), \(\chi_{\mathcal H ^ *}(G)\), denotes the minimum \(k\) such that \(G\) admits a partition of the vertices into \(k\) parts, each of which induces a disjoint union of graphs from \(\mathcal H\). When \(\mathcal H = \{K_1\}\), we have \(\chi_{\mathcal H ^ *}(G) = \chi (G)\). Generalizing a well-known result of Erdős about \(\chi\), the authors observe that for any finite \(\mathcal H\) it follows from the result of Erdős that there exist graphs \(G\) of arbitrarily high girth and arbitrary given \(\mathcal H\)-restricted chromatic number of \(G\), \(\chi_{\mathcal H ^ *}(G)\). They proceed to prove, by a probabilistic argument, that these graphs can be chosen so that \(\chi_{\mathcal H ^ *}(G) = \chi (G)\). For a graph \(H\), the \(H\)-forbidden chromatic number of \(G\), \(\chi_{H'}(G)\), is the minimum \(k\) such that \(G\) admits a partition of the vertices into \(k\) parts, each inducing an \(H\)-free subgraph of \(G\). The authors also prove that if \(H\) has girth at least \(g\), then there exist graphs \(G\) of girth at least \(g\) and arbitrarily high \(H\)-forbidden chromatic number of \(G\), \(\chi_{H'}(G)\). Answering earlier questions due to \textit{M. L. Weaver} and \textit{D. B. West} [Graphs Comb. 10, No. 1, 75-93 (1994; Zbl 0796.05036)], they also analyze \(\chi_{\mathcal H ^ *}(G)\) when \(\mathcal H\) consists of a single path and \(G\) is the Cartesian product of odd cycles. Finally they relate versions of these generalized chromatic numbers of lexicographic products to the circular chromatic numbers.
    0 references
    0 references
    relaxed coloring
    0 references
    \(P\)-chromatic number
    0 references
    girth
    0 references
    circular chromatic number
    0 references

    Identifiers