Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFour proofs of the directed Brooks Theorem
162
0
0.0
(
0
)
Added by
Pierre Aboulker
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We give four new proofs of the directed version of Brooks Theorem and an NP-completeness result.
rate research
Read More
A graph where each vertex $v$ has a list $L(v)$ of available colors is $L$-colorable if there is a proper coloring such that the color of $v$ is in $L(v)$ for each $v$. A graph is $k$-choosable if every assignment $L$ of at least $k$ colors to each vertex guarantees an $L$-coloring. Given a list assignment $L$, an $L$-request for a vertex $v$ is a color $cin L(v)$. In this paper, we look at a variant of the widely studied class of precoloring extension problems from [Z. Dvov{r}ak, S. Norin, and L. Postle: List coloring with requests. J. Graph Theory 2019], wherein one must satisfy enough, as opposed to all, of the requested set of precolors. A graph $G$ is $varepsilon$-flexible for list size $k$ if for any $k$-list assignment $L$, and any set $S$ of $L$-requests, there is an $L$-coloring of $G$ satisfying an $varepsilon$-fraction of the requests in $S$. It is conjectured that planar graphs are $varepsilon$-flexible for list size $5$, yet it is proved only for list size $6$ and for certain subclasses of planar graphs. We give a stronger version of the main tool used in the proofs of the aforementioned results. By doing so, we improve upon a result by Masav{r}ik and show that planar graphs without $K_4^-$ are $varepsilon$-flexible for list size $5$. We also prove that planar graphs without $4$-cycles and $3$-cycle distance at least 2 are $varepsilon$-flexible for list size $4$. Finally, we introduce a new (slightly weaker) form of $varepsilon$-flexibility where each vertex has exactly one request. In that setting, we provide a stronger tool and we demonstrate its usefulness to further extend the class of graphs that are $varepsilon$-flexible for list size $5$.
This paper proves a corner occupying theorem for the two-dimensional integral rectangle packing problem, stating that if it is possible to orthogonally place n arbitrarily given integral rectangles into an integral rectangular container without overlapping, then we can achieve a feasible packing by successively placing an integral rectangle onto a bottom-left corner in the container. Based on this theorem, we might develop efficient heuristic algorithms for solving the integral rectangle packing problem. In fact, as a vague conjecture, this theorem has been implicitly mentioned with different appearances by many people for a long time.
The canonical tree-decomposition theorem, given by Robertson and Seymour in their seminal graph minors series, turns out to be one of the most important tool in structural and algorithmic graph theory. In this paper, we provide the canonical tree decomposition theorem for digraphs. More precisely, we construct directed tree-decompositions of digraphs that distinguish all their tangles of order $k$, for any fixed integer $k$, in polynomial time. As an application of this canonical tree-decomposition theorem, we provide the following result for the directed disjoint paths problem: For every fixed $k$ there is a polynomial-time algorithm which, on input $G$, and source and terminal vertices $(s_1, t_1), dots, (s_k, t_k)$, either 1. determines that there is no set of pairwise vertex-disjoint paths connecting each source $s_i$ to its terminal $t_i$, or 2.finds a half-integral solution, i.e., outputs paths $P_1, dots, P_k$ such that $P_i$ links $s_i$ to $t_i$, so that every vertex of the graph is contained in at most two paths. Given known hardness results for the directed disjoint paths problem, our result cannot be improved for general digraphs, neither to fixed-parameter tractability nor to fully vertex-disjoint directed paths. As far as we are aware, this is the first time to obtain a tractable result for the $k$-disjoint paths problem for general digraphs. We expect more applications of our canonical tree-decomposition for directed results.
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 set of states in the puzzle, and the second player must then convert one randomly-selected state to another without passing through forbidden states. Analyzing this version raises the question of the treewidth of Hanoi graphs. We find this number exactly for three-peg puzzles and provide nearly-tight asymptotic bounds for larger numbers of pegs.
We prove the vanishing of the cup product of the bounded cohomology classes associated to any two Brooks quasimorphisms on the free group. This is a consequence of the vanishing of the square of a universal class for tree automorphism groups.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
