Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSolving the clique cover problem on (bull, $C_4$)-free graphs
187
0
0.0
(
0
)
Added by
Chinh Hoang
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We give an $O(n^4)$ algorithm to find a minimum clique cover of a (bull, $C_4$)-free graph, or equivalently, a minimum colouring of a (bull, $2K_2$)-free graph, where $n$ is the number of vertices of the graphs.
rate research
Read More
Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval graphs. The MAXIMUM CLIQUE problem, or the problem of finding the size of the maximum clique, is known to be NP-complete for $t$-interval graphs when $tgeq 3$ and polynomial-time solvable when $t=1$. The problem is also known to be NP-complete in $t$-track graphs when $tgeq 4$ and polynomial-time solvable when $tleq 2$. We show that MAXIMUM CLIQUE is already NP-complete for unit 2-interval graphs and unit 3-track graphs. Further, we show that the problem is APX-complete for 2-interval graphs, 3-track graphs, unit 3-interval graphs and unit 4-track graphs. We also introduce two new classes of graphs called $t$-circular interval graphs and $t$-circular track graphs and study the complexity of the MAXIMUM CLIQUE problem in them. On the positive side, we present a polynomial time $t$-approximation algorithm for WEIGHTED MAXIMUM CLIQUE on $t$-interval graphs, improving earlier work with approximation ratio $4t$.
An $(m, n)$-colored mixed graph is a graph having arcs of $m$ different colors and edges of $n$ different colors. A graph homomorphism of an $(m, n$)-colored mixed graph $G$ to an $(m, n)$-colored mixed graph $H$ is a vertex mapping such that if $uv$ is an arc (edge) of color $c$ in $G$, then $f(u)f(v)$ is also an arc (edge) of color $c$. The ($m, n)$-colored mixed chromatic number of an $(m, n)$-colored mixed graph $G$, introduced by Nev{s}etv{r}il and Raspaud [J. Combin. Theory Ser. B 2000] is the order (number of vertices) of the smallest homomorphic image of $G$. Later Bensmail, Duffy and Sen [Graphs Combin. 2017] introduced another parameter related to the $(m, n)$-colored mixed chromatic number, namely, the $(m, n)$-relative clique number as the maximum cardinality of a vertex subset which, pairwise, must have distinct images with respect to any colored homomorphism. In this article, we study the $(m, n$)-relative clique number for the family of subcubic graphs, graphs with maximum degree $Delta$, planar graphs and triangle-free planar graphs and provide new improved bounds in each of the cases. In particular, for subcubic graphs we provide exact value of the parameter.
Threshold graphs are a class of graphs that have many equivalent definitions and have applications in integer programming and set packing problems. A graph is said to have a threshold cover of size $k$ if its edges can be covered using $k$ threshold graphs. Chvatal and Hammer, in 1977, defined the threshold dimension $mathrm{th}(G)$ of a graph $G$ to be the least integer $k$ such that $G$ has a threshold cover of size $k$ and observed that $mathrm{th}(G)geqchi(G^*)$, where $G^*$ is a suitably constructed auxiliary graph. Raschle and Simon~[Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC 95, pages 650--661, 1995] proved that $mathrm{th}(G)=chi(G^*)$ whenever $G^*$ is bipartite. We show how the lexicographic method of Hell and Huang can be used to obtain a completely new and, we believe, simpler proof for this result. For the case when $G$ is a split graph, our method yields a proof that is much shorter than the ones known in the literature.
For which graphs $F$ is there a sparse $F$-counting lemma in $C_4$-free graphs? We are interested in identifying graphs $F$ with the property that, roughly speaking, if $G$ is an $n$-vertex $C_4$-free graph with on the order of $n^{3/2}$ edges, then the density of $F$ in $G$, after a suitable normalization, is approximately at least the density of $F$ in an $epsilon$-regular approximation of $G$. In recent work, motivated by applications in extremal and additive combinatorics, we showed that $C_5$ has this property. Here we construct a family of graphs with the property.
A hole is a chordless cycle with at least four vertices. A pan is a graph which consists of a hole and a single vertex with precisely one neighbor on the hole. An even hole is a hole with an even number of vertices. We prove that a (pan, even hole)-free graph can be decomposed by clique cutsets into essentially unit circular-arc graphs. This structure theorem is the basis of our $O(nm)$-time certifying algorithm for recognizing (pan, even hole)-free graphs and for our $O(n^{2.5}+nm)$-time algorithm to optimally color them. Using this structure theorem, we show that the tree-width of a (pan, even hole)-free graph is at most 1.5 times the clique number minus 1, and thus the chromatic number is at most 1.5 times the clique number.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
