×

On monochromatic frames in graphs. (English) Zbl 1314.05073

Summary: For a nontrivial connected graph \(G\) of order \(n\), let \(c: V(G)\to\mathbb{Z}_2\) be a vertex coloring of \(G\) where \(c(v)\neq 0\) for at least one vertex \(v\) of \(G\). Then the coloring \(c\) induces a new coloring \(\sigma: V(G)\to\mathbb{Z}_2\) of \(G\) defined by \(\sigma(v)=\sum_{u\in N[v]} c(n)\), where \(N[v]\) is the closed neighborhood of \(v\) and addition is performed in \(\mathbb{Z}_2\). If \(\sigma(v)= 0\in\mathbb{Z}_2\) for every vertex \(v\) in \(G\), then the coloring \(c\) is called a monochromatic \((2,0)\)-coloring of \(G\). A graph \(G\) having a monochromatic \((2,0)\)-coloring is a monochromatic \((2,0)\)-colorable graph. The minimum number of vertices colored 1 in a monochromatic \((2,0)\)-coloring of \(G\) is the \((2, 0)\)-chromatic number \(\chi_{(2,0)}(G)\) of \(G\). A graph \(G\) is called an odd-degree graph if every vertex of \(G\) has odd degree.
For a nontrivial odd-degree graph \(H\), a connected graph \(G\neq H\) is a monochromatic \((2,0)\)-frame of \(H\) if \(G\) has a minimum monochromatic \((2,0)\)-coloring \(c\) such that the subgraph induced by the vertices colored 1 by \(c\) is \(H\). The monochromatic frame number of \(H\) is defined as \(fn(H)= \min\{|V(G)- V(H)|\}\), where the minimum is taken over all monochromatic \((2,0)\)-frames \(G\) of \(H\). A monochromatic \((2,0)\)-colorable graph \(G\) of order \(n\) is a \((2,0)\)-extremal graph if \(\chi_{X(2,0)}(G)= n\). It is shown that \(fn(H)\leq 2\) for every connected \((2,0)\)-extremal graph \(H\) and the monochromatic frame numbers are determined for several well-known classes of \((2,0)\)-extremal graphs. Furthermore, it is shown that if \(H\) is the union of \(k\geq 2\) connected \((2,0)\)-extremal graphs, then \(fn(H)= k-1\). Other results and questions are also presented on monochromatic \((2,0)\)-frames in graphs.

MSC:

05C15 Coloring of graphs and hypergraphs