pith. sign in

arxiv: 1307.6443 · v1 · pith:LQ3OMK4Lnew · submitted 2013-07-24 · 🧮 math.CO

Clique numbers of graph unions

classification 🧮 math.CO
keywords cliqueadditiveadjacentgraphgraphsleastnumberssimple
0
0 comments X p. Extension
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.