Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDecomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules
135
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph $G$ is called interval colorable if it has a proper edge coloring with colors $1,2,3,dots$ such that the colors of the edges incident to every vertex of $G$ form an interval of integers. Not all graphs are interval colorable; in fact, quite few families have been proved to admit interval colorings. In this paper we introduce and investigate a new notion, the interval coloring thickness of a graph $G$, denoted ${theta_{mathrm{int}}}(G)$, which is the minimum number of interval colorable edge-disjoint subgraphs of $G$ whose union is $G$. Our investigation is motivated by scheduling problems with compactness requirements, in particular, problems whose solution may consist of several schedules, but where each schedule must not contain any waiting periods or idle times for all involved parties. We first prove that every connected properly $3$-edge colorable graph with maximum degree $3$ is interval colorable, and using this result, we deduce an upper bound on ${theta_{mathrm{int}}}(G)$ for general graphs $G$. We demonstrate that this upper bound can be improved in the case when $G$ is bipartite, planar or complete multipartite and consider some applications in timetabling.
rate research
Read More
A graph is locally irregular if any pair of adjacent vertices have distinct degrees. A locally irregular decomposition of a graph $G$ is a decomposition $mathcal{D}$ of $G$ such that every subgraph $H in mathcal{D}$ is locally irregular. A graph is said to be decomposable if it admits a locally irregular decomposition. We prove that any decomposable split graph can be decomposed into at most three locally irregular subgraphs and we characterize all split graphs whose decomposition can be into one, two or three locally irregular subgraphs.
We prove that for $k in mathbb{N}$ and $d leq 2k+2$, if a graph has maximum average degree at most $2k + frac{2d}{d+k+1}$, then $G$ decomposes into $k+1$ pseudoforests, where one of the pseudoforests has all connected components having at most $d$ edges.
Given a graph $G$, a decomposition of $G$ is a partition of its edges. A graph is $(d, h)$-decomposable if its edge set can be partitioned into a $d$-degenerate graph and a graph with maximum degree at most $h$. For $d le 4$, we are interested in the minimum integer $h_d$ such that every planar graph is $(d,h_d)$-decomposable. It was known that $h_3 le 4$, $h_2le 8$, and $h_1 = infty$. This paper proves that $h_4=1, h_3=2$, and $4 le h_2 le 6$.
For a real constant $alpha$, let $pi_3^alpha(G)$ be the minimum of twice the number of $K_2$s plus $alpha$ times the number of $K_3$s over all edge decompositions of $G$ into copies of $K_2$ and $K_3$, where $K_r$ denotes the complete graph on $r$ vertices. Let $pi_3^alpha(n)$ be the maximum of $pi_3^alpha(G)$ over all graphs $G$ with $n$ vertices. The extremal function $pi_3^3(n)$ was first studied by GyH{o}ri and Tuza [Decompositions of graphs into complete subgraphs of given order, Studia Sci. Math. Hungar. 22 (1987), 315--320]. In a recent progress on this problem, Kral, Lidicky, Martins and Pehova [Decomposing graphs into edges and triangles, Combin. Prob. Comput. 28 (2019) 465--472] proved via flag algebras that $pi_3^3(n)le (1/2+o(1))n^2$. We extend their result by determining the exact value of $pi_3^alpha(n)$ and the set of extremal graphs for all $alpha$ and sufficiently large $n$. In particular, we show for $alpha=3$ that $K_n$ and the complete bipartite graph $K_{lfloor n/2rfloor,lceil n/2rceil}$ are the only possible extremal examples for large $n$.
In 2006, Barat and Thomassen posed the following conjecture: for each tree $T$, there exists a natural number $k_T$ such that, if $G$ is a $k_T$-edge-connected graph and $|E(G)|$ is divisible by $|E(T)|$, then $G$ admits a decomposition into copies of $T$. This conjecture was verified for stars, some bistars, paths of length $3$, $5$, and $2^r$ for every positive integer $r$. We prove that this conjecture holds for paths of any fixed length.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
