Decomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules

DOI10.1016/J.DAM.2022.07.015zbMATH Open1514.05127arXiv2106.03531OpenAlexW3167501677MaRDI QIDQ6041828FDOQ6041828

Authors: Armen S. Asratian, Carl Johan Casselgren, P. A. Petrosyan 

Publication date: 15 May 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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 $het{a}_{mathrmint}(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 $het{a}_{mathrmint}(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.

Full work available at URL: https://arxiv.org/abs/2106.03531

Recommendations

• Interval edge-coloring: A model of curriculum scheduling
• Interval edge-colorings of composition of graphs
• On interval \(\Delta\)-coloring of bipartite graphs
• scientific article; zbMATH DE number 1990715
• Interval incidence graph coloring

zbMATH Keywords

graph coloringschedulingedge coloringinterval edge coloring

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Introduction to algorithms.
• Edge-Disjoint Spanning Trees of Finite Graphs
• Title not available (Why is that?)
• On the deficiency of bipartite graphs
• Investigation on interval edge-colorings of graphs
• On interval colourings of bi-regular bipartite graphs
• Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs
• On cyclically-interval edge colorings of trees
• Title not available (Why is that?)
• Open Shop Scheduling to Minimize Finish Time
• Title not available (Why is that?)
• Title not available (Why is that?)
• Interval colorings of edges of a multigraph
• Interval non-edge-colorable bipartite graphs and multigraphs
• Compact scheduling of zero-one time operations in multi-stage systems
• Title not available (Why is that?)
• A Theorem on Coloring the Lines of a Network
• Planar graphs: Theory and algorithms
• Link scheduling in wireless sensor networks: distributed edge-coloring revisited
• Title not available (Why is that?)
• Proper path‐factors and interval edge‐coloring of (3,4)‐biregular bigraphs
• Interval coloring of (3, 4)-biregular bigraphs having two (2,3)-biregular bipartite subgraphs
• On the thickness and arboricity of a graph
• On Vizing's bound for the chromatic index of a multigraph
• On interval and cyclic interval edge colorings of \((3, 5)\)-biregular graphs
• On interval edge colorings of biregular bipartite graphs with small vertex degrees
• Cyclic deficiency of graphs
• Some results on cyclic interval edge colorings of graphs
• Integer programming formulations for minimum deficiency interval coloring
• On interval edge-colorings of outerplanar graphs.

Cited In (4)

• A note on interval colourings of graphs
• Interval colourable orientations of graphs
• Interval colorings of graphs—Coordinated and unstable no‐wait schedules
• On interval colouring reorientation number of oriented graphs

This page was built for publication: Decomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041828)