Clique numbers of graph unions
pith:LQ3OMK4L Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{LQ3OMK4L}
Prints a linked pith:LQ3OMK4L badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
Let $B$ and $R$ be two simple graphs with vertex set $V$, and let $G(B,R)$ be the simple graph with vertex set $V$, in which two vertices are adjacent if they are adjacent in at least one of $B$ and $R$. For $X \subseteq V$, we denote by $B|X$ the subgraph of $B$ induced by $X$; let $R|X$ and $G(B,R)|X$ be defined similarly. We say that the pair $(B,R)$ is {\em additive} if for every $X \subseteq V$, the sum of the clique numbers of $B|X$ and $R|X$ is at least the clique number of $G(B,R)|X$. In this paper we give a necessary and sufficient characterization of additive pairs of graphs. This is a numerical variant of a structural question studied in \cite{ABC}.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.