Zobrazeno 1 - 10
of 76
pro vyhledávání: '"Penev, Irena"'
A minimal separator of a graph $G$ is a set $S \subseteq V(G)$ such that there exist vertices $a,b \in V(G) \setminus S$ with the property that $S$ separates $a$ from $b$ in $G$, but no proper subset of $S$ does. For an integer $k\ge 0$, we say that
Externí odkaz:
http://arxiv.org/abs/2312.10830
A ring is a graph $R$ whose vertex set can be partitioned into $k \geq 4$ nonempty sets, $X_1, \dots, X_k$, such that for all $i \in \{1,\dots,k\}$, the set $X_i$ can be ordered as $X_i = \{u_i^1, \dots, u_i^{|X_i|}\}$ so that $X_i \subseteq N_R[u_i^
Externí odkaz:
http://arxiv.org/abs/1907.11905
As usual, $P_n$ ($n \geq 1$) denotes the path on $n$ vertices, and $C_n$ ($n \geq 3$) denotes the cycle on $n$ vertices. For a family $\mathcal{H}$ of graphs, we say that a graph $G$ is $\mathcal{H}$-free if no induced subgraph of $G$ is isomorphic t
Externí odkaz:
http://arxiv.org/abs/1803.03315
Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (e.g. the class of perfect graphs and the class of even-hole-free graphs), appearing both as excluded config
Externí odkaz:
http://arxiv.org/abs/1707.03252
Publikováno v:
Journal of Graph Theory; Oct2024, Vol. 106 Issue 4, p816-842, 27p
Publikováno v:
Algorithmica 80, 415-447 (2018)
An ISK4 in a graph G is an induced subgraph of G that is isomorphic to a subdivision of K4 (the complete graph on four vertices). A wheel is a graph that consists of a chordless cycle, together with a vertex that has at least three neighbors in the c
Externí odkaz:
http://arxiv.org/abs/1602.02916
An ISK4 in a graph G is an induced subgraph of G that is isomorphic to a subdivision of K4 (the complete graph on four vertices). A wheel is a graph that consists of a chordless cycle, together with a vertex that has at least three neighbors in the c
Externí odkaz:
http://arxiv.org/abs/1602.02406
Autor:
Penev, Irena
Given a graph G, χ(G) denotes the chromatic number of G, and ω(G) denotes the clique number of G (i.e. the maximum number of pairwise adjacent vertices in G). A graph G is perfect provided that for every induced subgraph H of G, χ(H) = ω(H). This
Publikováno v:
Journal of Combinatorial Theory, Series B, 116:456-464, 2016
We prove that there exist perfect graphs of arbitrarily large clique-chromatic number. These graphs can be obtained from cobipartite graphs by repeatedly gluing along cliques. This negatively answers a question raised by Duffus, Sands, Sauer, and Woo
Externí odkaz:
http://arxiv.org/abs/1506.08628