ﻻ يوجد ملخص باللغة العربية
Two (proper) colorings of a graph are adjacent if they differ on exactly one vertex. Jerrum proved that any $(d + 2)$-coloring of any d-degenerate graph can be transformed into any other via a sequence of adjacent colorings. A result of Bonamy et al. ensures that a shortest transformation can have a quadratic length even for $d = 1$. Bousquet and Perarnau proved that a linear transformation exists for between $(2d + 2)$-colorings. It is open to determine if this bound can be reduced. In this note, we prove that it can be reduced for graphs of treewidth 2, which are 2-degenerate. There exists a linear transformation between 5-colorings. It completes the picture for graphs of treewidth 2 since there exist graphs of treewidth 2 such a linear transformation between 4-colorings does not exist.
The objective of the well-known Towers of Hanoi puzzle is to move a set of disks one at a time from one of a set of pegs to another, while keeping the disks sorted on each peg. We propose an adversarial variation in which the first player forbids a s
For a graph $G$ and integer $qgeq 2$, an edge $q$-coloring of $G$ is an assignment of colors to edges of $G$, such that edges incident on a vertex span at most $q$ distinct colors. The maximum edge $q$-coloring problem seeks to maximize the number of
A graph $G$ is said to be the intersection of graphs $G_1,G_2,ldots,G_k$ if $V(G)=V(G_1)=V(G_2)=cdots=V(G_k)$ and $E(G)=E(G_1)cap E(G_2)capcdotscap E(G_k)$. For a graph $G$, $mathrm{dim}_{COG}(G)$ (resp. $mathrm{dim}_{TH}(G)$) denotes the minimum num
The thinness of a graph is a width parameter that generalizes some properties of interval graphs, which are exactly the graphs of thinness one. Many NP-complete problems can be solved in polynomial time for graphs with bounded thinness, given a suita
For any class $mathcal{C}$ of bipartite graphs, we define quasi-$cal C$ to be the class of all graphs $G$ such that every bipartition of $G$ belongs to $cal C$. This definition is motivated by a generalisation of the switch Markov chain on perfect ma