Unit incomparability dimension and clique cover width in graphs

MaRDI QIDQ2869387zbMATH OpenFDO

Authors Farhad Shahrokhi

Publication date 3 January 2014

Published in Congressus Numerantium (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.04395

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: For a clique cover $C$ in the undirected graph $G$, the {it clique cover graph} of $C$ is the graph obtained by contracting the vertices of each clique in $C$ into a single vertex. The {it clique cover width} of $G$, denoted by $CCW(G)$, is the minimum value of the bandwidth of all clique cover graphs in $G$. Any $G$ with $CCW(G)=1$ is known to be an incomparability graph, and hence is called, a {it unit incomparability graph}. We introduced the {it unit incomparability dimension of $G$}, denoted by$Udim(G)$, to be the smallest integer $d$ so that there are unit incomparability graphs $H_i$ with $V(H_i)=V(G),i=1,2,\mathrm{...},d$, so that $E(G)=ca{p}_{i=1}^{d}E(G_i)$. We prove a decomposition theorem establishing the inequality $Udim(G)leCCW(G)$. Specifically, given any $G$, there are unit incomparability graphs $H_1,H_2,\mathrm{...},H_{CC(W)}$ with $V(H_i)=V(G)$ so that and $E(G)=ca{p}_{i=1}^{CCW}E(H_i)$. In addition, $H_i$ is co-bipartite, for $i=1,2,\mathrm{...},CCW(G)-1$. Furthermore, we observe that $CCW(G)ges(G)/2-1$, where $s(G)$ is the number of leaves in a largest induced star of $G$ , and use Ramsey Theory to give an upper bound on $s(G)$, when $G$ is represented as an intersection graph using our decomposition theorem. Finally, when $G$ is an incomparability graph we prove that $CCW(G)les(G)-1$.

Recommendations

• On the clique cover width problem
• Clique cover width and clique sum
• A new upper bound for the clique cover number with applications
• scientific article; zbMATH DE number 1439435
• Cover-incomparability graphs of posets

Cited in

(4)

• The inductive graph dimension from the minimum edge clique cover
• On the clique cover width problem
• scientific article; zbMATH DE number 1439435 (Why is no real title available?)
• Clique cover width and clique sum

This page was built for publication: Unit incomparability dimension and clique cover width in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2869387)