In this study, we address the independent set enumeration problem. Although several efficient enumeration algorithms and careful analyses have been proposed for maximal independent sets, no ...fine-grained analysis has been given for the non-maximal variant. As the main result, we propose an enumeration algorithm for the non-maximal variant that runs in O(q) amortized time and linear space, where q is the clique number, i.e., the maximum size of a clique in an input graph. Note that the proposed algorithm works correctly even if the exact value of q is unknown. It is optimal for graphs with a bounded clique number, such as, triangle-free graphs, bipartite graphs, planar graphs, bounded degenerate graphs, nowhere dense graphs, and F-free graphs for any fixed graph F, where a F-free graph is a graph that has no copy of F as a subgraph. Furthermore, with a slight modification of our proposed algorithm, we can enumerate independent sets with the size at most k in the same time and space complexity. This problem is a generalization of the original problem since this is equal to the original problem if k=n.
Prime ideal graphs of commutative rings Salih, Haval Mohammed; Jund, Asaad A.
Indonesian journal of combinatorics,
06/2022, Volume:
6, Issue:
1
Journal Article
Peer reviewed
Open access
Let R be a finite commutative ring with identity and P be a prime ideal of R. The vertex set is R - {0} and two distinct vertices are adjacent if their product in P. This graph is called the prime ...ideal graph of R and denoted by ΓP. The relationship among prime ideal, zero-divisor, nilpotent and unit graphs are studied. Also, we show that ΓP is simple connected graph with diameter less than or equal to two and both the clique number and the chromatic number of the graph are equal. Furthermore, it has girth 3 if it contains a cycle. In addition, we compute the number of edges of this graph and investigate some properties of ΓP.
Let G be a graph with set of vertices V(G)(|V(G)|=n) and edge set E(G). Very recently, a new degree-based molecular structure descriptor, called Sombor index is denoted by SO(G) and is defined as ...SO=SO(G)=∑vivj∈E(G)dG(vi)2+dG(vj)2, where dG(vi) is the degree of the vertex vi in G. In this paper we present some lower and upper bounds on the Sombor index of graph G in terms of graph parameters (clique number, chromatic number, number of pendant vertices, etc.) and characterize the extremal graphs.
Extending the idea from the recent paper by Carbonero, Hompe, Moore, and Spirkl, for every function
f
:
N
→
N
∪
{
∞
}
with
f
(
1
)
=
1
and
f
(
n
)
⩾
3
n
+
1
3
, we construct a hereditary class of ...graphs
G
such that the maximum chromatic number of a graph in
G
with clique number
n
is equal to
f
(
n
) for every
n
∈
N
. In particular, we prove that there exist hereditary classes of graphs that are
χ
-bounded but not polynomially
χ
-bounded.
For a graph G $G$, let χ(
G
) $\chi (G)$ (ω(
G
) $\omega (G)$) denote its chromatic (clique) number. A P
2
+
P
3 ${P}_{2}+{P}_{3}$ is the graph obtained by taking the disjoint union of a two‐vertex ...path P
2 ${P}_{2}$ and a three‐vertex path P
3 ${P}_{3}$. A P
2
+
P
3
¯ $\bar{{P}_{2}+{P}_{3}}$ is the complement graph of a P
2
+
P
3 ${P}_{2}+{P}_{3}$. In this paper, we study the class of (P
2
+
P
3
,
P
2
+
P
3
¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graphs and show that every such graph G $G$ with ω(
G
)
≥
3 $\omega (G)\ge 3$ satisfies χ(
G
)
≤
max{ω(
G
)
+
3
,⌊3
2
ω(
G
)
⌋
−
1
} $\chi (G)\le \max \{\omega (G)+3,\lfloor \phantom{\rule-0.5em{}{0ex}}\frac{3}{2}\omega (G)\rfloor -1\}$. Moreover, the bound is tight. Indeed, for any k
∈
N $k\in {\mathbb{N}}$ and k
≥
3 $k\ge 3$, there is a (P
2
+
P
3
,
P
2
+
P
3
¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graph G $G$ with ω(
G
)
=
k $\omega (G)=k$ and χ(
G
)
=
max{k
+
3
,⌊3
2
k
⌋
−
1
} $\chi (G)=\max \{k+3,\lfloor \phantom{\rule-0.5em{}{0ex}}\frac{3}{2}k\rfloor -1\}$.
Let Gn$$ {G}_n $$ be a random geometric graph, and then for q,p∈0,1)$$ q,p\in \left0,1\right) $$ we construct a (q,p)$$ \left(q,p\right) $$‐perturbed noisy random geometric graph Gnq,p$$ {G}_n^{q,p} ...$$ where each existing edge in Gn$$ {G}_n $$ is removed with probability q$$ q $$, while and each non‐existent edge in Gn$$ {G}_n $$ is inserted with probability p$$ p $$. We give asymptotically tight bounds on the clique number ωGnq,p$$ \omega \left({G}_n^{q,p}\right) $$ for several regimes of parameter.
A hole is an induced cycle of length at least 4, and an even-hole is a hole of even length. A cap is a graph consisting of a hole and an additional vertex which is adjacent to exactly two adjacent ...vertices of the hole. Cameron et al. 3 proved that every (cap, even-hole)-free graph G has χ(G)⩽⌊32ω(G)⌋, and they also proposed a question stating that if χ(G)⩽⌈54ω(G)⌉ for all (cap, even-hole)-free graphs. Wu and Xu 20 showed that every (cap, even-hole)-free graph G has χ(G)⩽⌈43ω(G)⌉. In this paper, we improve this upper bound and show that every (cap, even-hole)-free graph has χ(G)⩽⌈97ω(G)⌉+1.
In 1985, Erdős and Nešetřil conjectured that the square of the line graph of a graph G, that is, L(G)2, can be colored with 54Δ(G)2 colors. This conjecture implies the weaker conjecture that the ...clique number of such a graph, that is, ω(L(G)2), is at most 54Δ(G)2. In 2015, Śleszyńska‐Nowak proved that ω(L(G)2)≤32Δ(G)2. In this paper, we prove that ω(L(G)2)≤43Δ(G)2. This theorem follows from our stronger result that ω(L(G)2)≤σ(G)2/3 where σ(G)≔maxuv∈E(G)d(u)+d(v)=Δ(L(G))+2.
We show that every connected induced subgraph of a graph G is dominated by an induced connected split graph if and only if G is C-free, where C is a set of six graphs which includes P7 and C7, and ...each containing an induced P5. A similar characterization is shown for the class of graphs which are dominated by an induced connected complete split graph. Motivated by these results, we study structural descriptions of some classes of (P7, C7)-free graphs. In particular, we give structural descriptions for the class of (P7, C7, C4, gem)-free graphs and for the class of (P7, C7, C4, diamond)-free graphs. Using these results, we show that every (P7, C7, C4, gem)-free graph G satisfies χ(G)≤2ω(G)−1, and that every (P7, C7, C4, diamond)-free graph H satisfies χ(H)≤max{3,ω(H)}.
Given two graphs
H
1 and
H
2, a graph is
(
H
1
,
H
2
)‐free if it contains no induced subgraph isomorphic to
H
1 or
H
2. For a positive integer
t,
P
t is the chordless path on
t vertices. A ...paraglider is the graph that consists of a chorless cycle
C
4 plus a vertex adjacent to three vertices of the
C
4. In this paper, we study the structure of (
P
5, paraglider)‐free graphs, and show that every such graph
G satisfies
χ
(
G
)
≤
⌈
3
2
ω
(
G
)
⌉, where
χ
(
G
) and
ω
(
G
) are the chromatic number and clique number of
G, respectively. Our bound is attained by the complement of the Clebsch graph on 16 vertices. More strongly, we completely characterize all the (
P
5, paraglider)‐free graphs
G that satisfies
χ
(
G
)
>
3
2
ω
(
G
). We also construct an infinite family of (
P
5, paraglider)‐free graphs such that every graph
G in the family has
χ
(
G
)
=
⌈
3
2
ω
(
G
)
⌉
−
1. This shows that our upper bound is optimal up to an additive constant and that there is no
(
3
2
−
ϵ
)‐approximation algorithm for the chromatic number of (
P
5, paraglider)‐free graphs for any
ϵ
>
0.
PDF
