Results 1 to 10 of about 1,168 (127)
Sombor characteristic values of cographs [PDF]
HeliyonA unique class of cograph is examined, that is defined recursively as C=C(n1)=K‾n1, and C=C(n1,n2,…,ni)=C(n1,n2,…,ni−1)∪Kni‾, for 2≤i≤k. The Sombor spectrum of C is calculated, the Sombor spectral radius and establish the sharp bounds for the Sombor ...
Zahid Raza +2 more
doaj +4 more sources
The micro-world of cographs [PDF]
Discrete Applied Mathematics, 2020 Cographs constitute a small point in the atlas of graph classes. However, by zooming in on this point, we discover a complex world, where many parameters jump from finiteness to infinity. In the present paper, we identify several milestones in the world of cographs and create a hierarchy of graph parameters grounded on these milestones.
Bogdan Alecu +2 more
openaire +3 more sources
Theory and Applications of GraphsA class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by G^{apex} the class of graphs G that contain a vertex v such that G − v is in G.
Jagdeep Singh +2 more
doaj +5 more sources
Generalizing Cographs to 2-Cographs
The Electronic Journal of Combinatorics, 2023 A graph in which every connected induced subgraph has a disconnected complement is called a cograph. Such graphs are precisely the graphs that do not have the 4-vertex path as an induced subgraph. We define a $2$-cograph to be a graph in which the complement of every $2$-connected induced subgraph is not $2$-connected.
Oxley, James, Singh, Jagdeep
openaire +2 more sources
An Analytic Propositional Proof System on Graphs [PDF]
Logical Methods in Computer Science, 2022 In this paper we present a proof system that operates on graphs instead of formulas. Starting from the well-known relationship between formulas and cographs, we drop the cograph-conditions and look at arbitrary undirected) graphs. This means that we lose
Matteo Acclavio +2 more
doaj +1 more source
P_4-Colorings and P_4-Bipartite Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 A vertex partition of a graph into disjoint subsets V_is is said to be a P_4-free coloring if each color class V_i induces a subgraph without chordless path on four vertices (denoted by P_4).
Chinh T. Hoàng, Van Bang Le
doaj +1 more source
On Rödl's Theorem for Cographs
The Electronic Journal of Combinatorics, 2023 A theorem of Rödl states that for every fixed $F$ and $\varepsilon>0$ there is $\delta=\delta_F(\varepsilon)$ so that every induced $F$-free graph contains a vertex set of size $\delta n$ whose edge density is either at most $\varepsilon$ or at least $1-\varepsilon$.
Gishboliner, Lior, Shapira, Asaf
openaire +1 more source
Capturing Polynomial Time using Modular Decomposition [PDF]
Logical Methods in Computer Science, 2019 The question of whether there is a logic that captures polynomial time is one of the main open problems in descriptive complexity theory and database theory.
Berit Grußien
doaj +1 more source
Erdős–Hajnal for graphs with no 5‐hole
Proceedings of the London Mathematical Society, Volume 126, Issue 3, Page 997-1014, March 2023., 2023 Abstract The Erdős–Hajnal conjecture says that for every graph H$H$ there exists τ>0$\tau >0$ such that every graph G$G$ not containing H$H$ as an induced subgraph has a clique or stable set of cardinality at least |G|τ$|G|^\tau$. We prove that this is true when H$H$ is a cycle of length five.
Maria Chudnovsky +3 more
wiley +1 more source
On the path partition number of 6‐regular graphs
Journal of Graph Theory, Volume 101, Issue 3, Page 345-378, November 2022., 2022 Abstract A path partition (also referred to as a linear forest) of a graph G $G$ is a set of vertex‐disjoint paths which together contain all the vertices of G $G$. An isolated vertex is considered to be a path in this case. The path partition conjecture states that every n $n$‐vertex d $d$‐regular graph has a path partition with at most n d + 1 $\frac{
Uriel Feige, Ella Fuchs
wiley +1 more source