The representation number of a graph is the smallest integer k such that the graph can be represented by a word in which each vertex appears exactly k times, and two distinct vertices x and y alternate in the word if and only if they are adjacent in the graph. We extend known results on the representation number for various graph classes to chessboard graphs—namely, king, queen, rook, bishop, and knight graphs. We provide a complete classification for queen graphs and partial classifications or observations for the other classes. As a consequence of our study, we obtain a characterization of all chessboard graphs that are circle graphs. Our work also leads to several interesting open problems.
For planar graphs, it is known that their treewidth is bounded by $O(\sqrt{n})$, where $n$ is the number of vertices of the graph. A related invariant to treewidth, is the scramble number of graphs. Recently, Connor et. al proved that planar graphs of bounded maximal degree have scramble number bounded by $O(\sqrt{n})$...
The representation number of a graph is the least positive integer $k$ for which its vertices can be arranged in a word, each occurring $k$ times, so that two distinct letters alternate precisely when the corresponding vertices are adjacent. We prove that every bipartite graph on $N\ge9$ vertices has representation num...
Matthew J. Colbrook, Catherine Drysdale· 0 citations
A graph is
perfect
if, for every induced subgraph, the chromatic number equals the size of its largest clique. In 1972, Lovász established a fundamental characterization of perfect graphs, showing that a graph is perfect if and only if, for every induced subgraph, the product of the size of the largest independen...
A graph $H$ is called common if the number of monochromatic copies of $H$ in a $2$-edge-coloring of a large complete graph is asymptotically minimized by the random coloring with an equal proportion of each color. The house graph and $K_4$ with one edge subdivided once are known to be common by the flag algebra method....
We prove that deciding whether a graph has lettericity at most k is NP-complete, even for four-colorable comparability graphs. Our reduction maps a bipartite graph G to the graph obtained from its incidence graph by inflating each vertex by a clique or an independent set of three vertices. The lettericity of this graph...
In the 1960s, Erd\H{o}s and Hajnal conjectured that every graph with sufficiently large chromatic number contains a subgraph of large girth (size of a smallest cycle) and large chromatic number. In this paper, we prove that every tournament with sufficiently large dichromatic number contains a subdigraph of large digir...
Pierre Charbit, Samuel Coulomb· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
