ﻻ يوجد ملخص باللغة العربية
The notion of a 12-representable graph was introduced by Jones et al.. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that any 12-representable graph is a comparability graph, and also that a tree is 12-representable if and only if it is a double caterpillar. Moreover, Jones et al. initiated the study of 12-representability of induced subgraphs of a grid graph, and asked whether it is possible to characterize such graphs. This question in is meant to be about induced subgraphs of a grid graph that consist of squares, which we call square grid graphs. However, an induced subgraph in a grid graph does not have to contain entire squares, and we call such graphs line grid graphs. In this paper we answer the question of Jones et al. by providing a complete characterization of $12$-representable square grid graphs in terms of forbidden induced subgraphs. Moreover, we conjecture such a characterization for the line grid graphs and give a number of results towards solving this challenging conjecture. Our results are a major step in the direction of characterization of all 12-representable graphs since beyond our characterization, we also discuss relations between graph labelings and 12-representability, one of the key open questions in the area.
A graph $G=(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$, $x eq y$, alternate in $w$ if and only if $(x,y)in E$. Halld{o}rsson et al. have shown that a graph is word-representable if and o
This exposition contains a short and streamlined proof of the recent result of Kwan, Letzter, Sudakov and Tran that every triangle-free graph with minimum degree $d$ contains an induced bipartite subgraph with average degree $Omega(ln d/lnln d)$.
In 1975 Bollobas, ErdH os, and Szemeredi asked the following question: given positive integers $n, t, r$ with $2le tle r-1$, what is the largest minimum degree $delta(G)$ among all $r$-partite graphs $G$ with parts of size $n$ and which do not contai
In this paper we study random induced subgraphs of the binary $n$-cube, $Q_2^n$. This random graph is obtained by selecting each $Q_2^n$-vertex with independent probability $lambda_n$. Using a novel construction of subcomponents we study the largest
For an integer $n>2$, a rank-$n$ matroid is called an $n$-spike if it consists of $n$ three-point lines through a common point such that, for all $kin{1, 2, ..., n - 1}$, the union of every set of $k$ of these lines has rank $k+1$. Spikes are very sp