A graph G is called interval colorable if it has a proper edge coloring with colors 1, 2, 3, ... 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 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 require-ments, 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 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.

The classical global criteria for the existence of Hamilton cycles only apply to graphs with large edge density and small diameter. In a series of papers Asratian and Khachatryan developed local criteria for the existence of Hamilton cycles in finite connected graphs, which are analogues of the classical global criteria due to Dirac (1952), Ore (1960), Jung (1978), and Nash-Williams (1971). The idea was to show that the global concept of Hamiltonicity can, under rather general conditions, be captured by local phenomena, using the structure of balls of small radii. (The ball of radius r centered at a vertex u is a subgraph of G induced by the set of vertices whose distances from u do not exceed r.) Such results are called localization theorems and present a possibility to extend known classes of finite Hamiltonian graphs. In this paper we formulate a general approach for finding localization theorems and use this approach to formulate local analogues of well-known results of Bauer et al. (1989), Bondy (1980), Haggkvist and Nicoghossian (1981), and Moon and Moser (1963). Finally we extend two of our results to infinite locally finite graphs and show that they guarantee the existence of Hamiltonian curves, introduced by Kundgen, Li and Thomassen (2017). (c) 2020 Elsevier Inc. All rights reserved.

In this paper we present some results for a connected infinite graph G with finite degrees where the properties of balls of small radii guarantee the existence of some Hamiltonian and connectivity properties of G. (For a vertex w of a graph G the ball of radius r centered at w is the subgraph of G induced by the set Mr(w) of vertices whose distance from w does not exceed r). In particular, we prove that if every ball of radius 2 in G is 2-connected and G satisfies the condition dG(u)+dG(v)≥|M2(w)|−1 for each path uwv in G, where u and v are non-adjacent vertices, then G has a Hamiltonian curve, introduced by Kündgen et al. (2017). Furthermore, we prove that if every ball of radius 1 in G satisfies Ore’s condition (1960) then all balls of any radius in G are Hamiltonian.

Den här boken är främst avsedd för grundläggande kurser i diskret matematik vid universitet och högskolor. Framför allt riktar den sig till första- och andraårsstudenter på data-, matematik-, civilingenjörs- och högskoleingenjörsprogrammen.

Let G be a Class 1 graph with maximum degree 4 and let t amp;gt;= 5 be an integer. We show that any proper t-edge coloring of G can be transformed to any proper 4-edge coloring of G using only transformations on 2-colored subgraphs (so-called interchanges). This settles the smallest previously unsolved case of a well-known problem of Vizing on interchanges, posed in 1965. Using our result we give an affirmative answer to a question of Mohar for two classes of graphs: we show that all proper 5-edge colorings of a Class 1 graph with maximum degree 4 are Kempe equivalent, that is, can be transformed to each other by interchanges, and that all proper 7-edge colorings of a Class 2 graph with maximum degree 5 are Kempe equivalent. (C) 2015 Wiley Periodicals, Inc.

The author and A. Mirumian proved the following theorem: Let G be a bipartite graph with maximum degree Delta and let t, n be integers, t andgt;= n andgt;= Delta. Then it is possible to obtain, from one proper edge t-coloring of G, any proper edge n-coloring of G using only transformations of 2-colored and 3-colored subgraphs such that the intermediate colorings are also proper. In this note we show that if t andgt; Delta then we can transform f to g using only transformations of 2-colored subgraphs. We also correct the algorithm suggested in [A.S. Asratian, Short solution of Kotzigs problem for bipartite graphs, J. Combin. Theory Set. B 74 (1998) 160-168] for transformation of f to g in the case when t = n = Delta and G is regular.

An interval coloring of a graph G is a proper coloring of E(G) by positive integers such that the colors on the edges incident to any vertex are consecutive. A (3,4)-biregular bigraph is a bipartite graph in which each vertex of one part has degree 3 and each vertex of the other has degree 4; it is unknown whether these all have interval colorings. We prove that G has an interval coloring using 6 colors when G is a (3,4)-biregular bigraph having a spanning subgraph whose components are paths with endpoints at 3-valent vertices and lengths in {2, 4, 6, 8}. We provide several sufficient conditions for the existence of such a subgraph.

A (3, 4)-biregular bigraph G is a bipartite graph where all vertices in one part have degree 3 and all vertices in the other part have degree 4. A path factor of G is a spanning subgraph whose components are nontrivial paths. We prove that a simple (3,4)-biregular bigraph always has a path factor such that the endpoints of each path have degree three. Moreover we suggest a polynomial algorithm for the construction of such a path factor.