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

DOI10.1016/J.DAM.2022.07.015MaRDI QIDQ6041828zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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