O.V. Borodin, Alexandr Kostochka, Matthew Yancey,
A graph G is (1,1)-colorable if its vertices can be partitioned into subsets V1 and V2 such that every vertex in G[Vi] has degree at most 1 for each i∈{1,2}. We prove that every graph with maximum average degree at most 145 is (1,1)-colorable. In particular, it follows that every planar graph with girth at least 7 is (1,1)-colorable. On the other hand, we construct graphs with maximum average degree arbitrarily close to 145 (from above) that are not (1,1)-colorable. In fact, we establish the best possible ...
Tópico(s): Graph Labeling and Dimension Problems
2013 - Elsevier BV | Discrete Mathematics
O. V. Borodin, Alexandr Kostochka,
A graph G is (j,k)-colorable if its vertices can be partitioned into subsets V1 and V2 such that every vertex in G[V1] has degree at most j and every vertex in G[V2] has degree at most k. We prove that if k⩾2j+2, then every graph with maximum average degree at most 2(2−k+2(j+2)(k+1)) is (j,k)-colorable. On the other hand, we construct graphs with the maximum average degree arbitrarily close to 2(2−k+2(j+2)(k+1)) (from above) that are not (j,k)-colorable. In fact, we prove a stronger result by establishing ...
Tópico(s): Advanced Graph Theory Research
2013 - Elsevier BV | Journal of Combinatorial Theory Series B
O. V. Borodin, Alexandr Kostochka, Bernard Lidický, Matthew Yancey,
A recent lower bound on the number of edges in a k-critical n-vertex graph by Kostochka and Yancey yields a half-page proof of the celebrated Gr\"otzsch Theorem that every planar triangle-free graph is 3-colorable. In this paper we use the same bound to give short proofs of other known theorems on 3-coloring of planar graphs, among whose is the Gr\"unbaum-Aksenov Theorem that every planar with at most three triangles is 3-colorable. We also prove the new result that every graph obtained from a triangle- ...
Tópico(s): Limits and Structures in Graph Theory
2013 - Elsevier BV | European Journal of Combinatorics
O.V. Borodin, Alexandr Kostochka,
A graph G is (1, 0)-colorable if its vertex set can be partitioned into subsets V 1 and V 0 so that in G[V 1] every vertex has degree at most 1, while G[V 0] is edgeless. We prove that every graph with maximum average degree at most $\tfrac{{12}} {5} $ is (1, 0)-colorable. In particular, every planar graph with girth at least 12 is (1, 0)-colorable. On the other hand, we construct graphs with the maximum average degree arbitrarily close (from above) to $\tfrac{{12}} {5} $ which are not (1, 0)-colorable. In fact, ...
Tópico(s): Advanced Graph Theory Research
2011 - Pleiades Publishing | Siberian Mathematical Journal
O. V. Borodin, Alexandr Kostochka, Naeem N. Sheikh, Gexin Yu,
W. He et al. showed that a planar graph of girth 11 can be decomposed into a forest and a matching. D. Kleitman et al. proved the same statement for planar graphs of girth 10. We further improve the bound on girth to 9.
Tópico(s): Graph Labeling and Dimension Problems
2007 - Elsevier BV | European Journal of Combinatorics
O. V. Borodin, Alexandr Kostochka, Bjarne Toft,
We introduce the concept of variable degeneracy of a graph extending that of k-degeneracy. This makes it possible to give a common generalization of the point partition numbers and the list chromatic number. In particular, the list point arboricity of a graph is considered. We extend Brooks' and Gallai's theorems in terms of covering the vertices of a graph by disjoint induced subgraphs G1,…,Gs such that Gi is strictly fi-degenerate, given nonnegative-integer-valued functions f1,…,fs whose sum is ...
Tópico(s): Graph Labeling and Dimension Problems
2000 - Elsevier BV | Discrete Mathematics
O.V. Borodin, Alexandr Kostochka, Jaroslav Nešetřil, André Raspaud, Éric Sopena,
The oriented chromatic number o(H) of an oriented graph H is defined as the minimum order of an oriented graph H′ such that H has a homomorphism to H′. The oriented chromatic number o(G) of an undirected graph G is then defined as the maximum oriented chromatic number of its orientations. In this paper we study the links between o(G) and mad(G) defined as the maximum average degree of the subgraphs of G.
Tópico(s): Retinoids in leukemia and cellular processes
1999 - Elsevier BV | Discrete Mathematics
O. V. Borodin, Alexandr Kostochka, Douglas R. Woodall,
A proper vertex-colouring of a graph is acyclic if there are no 2-coloured cycles. It is known that every planar graph is acyclically 5-colourable, and that there are planar graphs with acyclic chromatic number χa = 5 and girth g = 4. It is proved here that a planar graph satisfies χa ⩽ 4 if g ⩾ 5 and χa ⩽ 3 if g ⩾ 7.
Tópico(s): Advanced Graph Theory Research
1999 - Wiley | Journal of the London Mathematical Society
O. V. Borodin, Alexandr Kostochka, Douglas R. Woodall,
It is proved that ifGis a planar graph with total (vertex–edge) chromatic number χ″, maximum degree Δ and girthg, then χ″ = Δ+1 if Δ ≥ 5 andg ≥ 5, or Δ ≥ 4 andg ≥ 6, or Δ ≥ 3 andg ≥ 10. These results hold also for graphs in the projective plane, torus and Klein bottle.
Tópico(s): Graph Labeling and Dimension Problems
1998 - Elsevier BV | European Journal of Combinatorics
O. V. Borodin, Alexandr Kostochka, Douglas R. Woodall,
It is proved that a planar graph with maximum degree Δ ≥ 11 has total (vertex-edge) chromatic number $Delta; + 1. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 53–59, 1997
Tópico(s): Computational Geometry and Mesh Generation
1997 - Wiley | Journal of Graph Theory
O. V. Borodin, Alexandr Kostochka, D. R. Woodall,
It is proved that a planar graph with maximum degree Δ ≥ 11 has total (vertex-edge) chromatic number $Delta; + 1. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 53–59, 1997
Tópico(s): Advanced Graph Theory Research
1997 - Wiley | Journal of Graph Theory
O. V. Borodin, Alexandr Kostochka, Douglas R. Woodall,
This paper exploits the remarkable new method of Galvin (J. Combin. Theory Ser. B63(1995), 153–158), who proved that the list edge chromatic numberχ′list(G) of a bipartite multigraphGequals its edge chromatic numberχ′(G). It is now proved here that if every edgee=uwof a bipartite multigraphGis assigned a list of at least max{d(u), d(w)} colours, thenGcan be edge-coloured with each edge receiving a colour from its list. If every edgee=uwin an arbitrary multigraphGis assigned a list of at least max{ ...
Tópico(s): graph theory and CDMA systems
1997 - Elsevier BV | Journal of Combinatorial Theory Series B
O. V. Borodin, Alexandr Kostochka,
Tópico(s): Limits and Structures in Graph Theory
1977 - Elsevier BV | Journal of Combinatorial Theory Series B
O. V. Borodin, Alexandr Kostochka, Douglas R. Woodall,
We exploit the technique of Galvin (1995) to prove that an orientation D of a line-graph G (of a multigraph) is kernel-perfect if and only if every oriented odd cycle in D has a chord (or pseudochord) and every clique has a kernel.
Tópico(s): Limits and Structures in Graph Theory
1998 - Elsevier BV | Discrete Mathematics
O. V. Borodin, Zdeněk Dvořák, Alexandr Kostochka, Bernard Lidický, Matthew Yancey,
By the Grunbaum-Aksenov Theorem (extending Grotzsch's Theorem) every planar graph with at most three triangles is 3-colorable. However, there are infinitely many planar 4-critical graphs with exactly four triangles. We describe all such graphs. This answers a question of Erdos from 1990.
Tópico(s): Limits and Structures in Graph Theory
2014 - Elsevier BV | European Journal of Combinatorics
O. V. Borodin, Alexandr Kostochka, Naeem N. Sheikh, Gexin Yu,
Abstract The M‐degree of an edge xy in a graph is the maximum of the degrees of x and y . The M‐degree of a graph G is the minimum over M ‐degrees of its edges. In order to get upper bounds on the game chromatic number, He et al showed that every planar graph G without leaves and 4‐cycles has M ‐degree at most 8 and gave an example of such a graph with M ‐degree 3. This yields upper bounds on the game chromatic number of C 4 ‐free planar graphs. We determine the maximum possible M ‐degrees for planar, ...
Tópico(s): Computational Geometry and Mesh Generation
2008 - Wiley | Journal of Graph Theory
O. V. Borodin, Alexandr Kostochka, André Raspaud, Éric Sopena,
A coloring of graph vertices is called acyclic if the ends of each edge are colored in distinct colors and there are no two-colored cycles. Suppose each face of rank not greater thank, k ≥ 4, on a surfaceS N is replaced by the clique on the same set of vertices. Then the pseudograph obtained in this way can be colored acyclically in a set of colors whose cardinality depends linearly onN and onk. Results of this kind were known before only for 1 ≤N ≤ 2 and 3 ≤k ≤ 4.
Tópico(s): Graph Labeling and Dimension Problems
2000 - Pleiades Publishing | Mathematical Notes
O. V. Borodin, A. O. Ivanova, Alexandr Kostochka,
Lebesgue (1940) proved that every plane triangulation contains a face with the vertex-degrees majorized by one of the following triples: (3,6,∞),(3,7,41),(3,8,23),(3,9,17),(3,10,14),(3,11,13),(4,4,∞),(4,5,19),(4,6,11),(4,7,9),(5,5,9),(5,6,7). Jendrol' (1999) improved this description, except for (4,4,∞) and (4,6,11), to (3,4,35),(3,5,21),(3,6,20),(3,7,16),(3,8,14),(3,9,14),(3,10,13),(4,4,∞),(4,5,13),(4,6,17),(4,7,8),(5,5,7),(5,6,6) and conjectured that the tight description is (3,4,30),(3,5,18),(3,6,20),( ...
Tópico(s): Advanced Optimization Algorithms Research
2013 - Elsevier BV | Discrete Mathematics
O. V. Borodin, S.-J. Kim, Alexandr Kostochka, Douglas B. West,
We show that a planar graph with girth at least 20t−23 has circular chromatic number at most 2+1t, improving earlier results. This follows from a general result establishing homomorphisms into special targets for graphs with given girth and given maximum average degree. Other applications concern oriented chromatic number and homomorphisms into mixed graphs with colored edges.
Tópico(s): Graph Labeling and Dimension Problems
2003 - Elsevier BV | Journal of Combinatorial Theory Series B
O. V. Borodin, D. Fon-Der-Flaass, Alexandr Kostochka, André Raspaud, Éric Sopena,
For every positive integer k, we present an oriented graph Gk such that deleting any vertex of Gk decreases its oriented chromatic number by at least k and deleting any arc decreases the oriented chromatic number of Gk by two.
Tópico(s): Graph Labeling and Dimension Problems
2001 - Elsevier BV | Journal of Combinatorial Theory Series B
O.V. Borodin, A. O. Ivanova, Torben R. Jensen, Alexandr Kostochka, Matthew Yancey,
We prove that every normal plane map, as well as every 3-polytope, has a path on three vertices whose degrees are bounded from above by one of the following triplets: (3,3,∞), (3,4,11), (3,7,5), (3,10,4), (3,15,3), (4,4,9), (6,4,8), (7,4,7), and (6,5,6). No parameter of this description can be improved, as shown by appropriate 3-polytopes.
Tópico(s): Mathematics and Applications
2013 - Elsevier BV | Discrete Mathematics
O.V. Borodin, A. O. Ivanova, Alexandr Kostochka,
Abstract We prove that every normal plane map (NPM) has a path on three vertices (3‐path) whose degree sequence is bounded from above by one of the following triplets: (3, 3, ∞), (3,15,3), (3,10,4), (3,8,5), (4,7,4), (5,5,7), (6,5,6), (3,4,11), (4,4,9), and (6,4,7). This description is tight in the sense that no its parameter can be improved and no term dropped. We also pose a problem of describing all tight descriptions of 3‐paths in NPMs and make a modest contribution to it by showing that there exist precisely ...
Tópico(s): Advanced Graph Theory Research
2016 - Wiley | Journal of Graph Theory
Pavel M. Borodin, Ivan Gorlov, Alexandr I. Agulnik, Sergei I. Agulnik, A. Ruvinsky,
Tópico(s): DNA and Nucleic Acid Chemistry
1991 - Springer Science+Business Media | Chromosoma
O. V. Borodin, A. O. Ivanova, Alexandr Kostochka, Naeem N. Sheikh,
He, Hou, Lih, Shao, Wang, and Zhu showed that a planar graph of girth 11 can be decomposed into a forest and a matching. Borodin, Kostochka, Sheikh, and Yu improved the bound on girth to 9. We give sufficient conditions for a planar graph with 3-cycles to be decomposable into a forest and a matching.
Tópico(s): Limits and Structures in Graph Theory
2008 - Elsevier BV | Discrete Mathematics
O. V. Borodin, A. O. Ivanova, Alexandr Kostochka,
Let φP(C6) (respectively, φT(C6)) be the minimum integer k with the property that every 3-polytope (respectively, every plane triangulation) with minimum degree 5 has a 6-cycle with all vertices of degree at most k. In 1999, S. Jendrol' and T. Madaras proved that 10≤φT(C6)≤11. It is also known, due to B. Mohar, R. Škrekovski and H.-J. Voss (2003), that φP(C6)≤107. We prove that φP(C6)=φT(C6)=11.
Tópico(s): Computational Geometry and Mesh Generation
2013 - Elsevier BV | Discrete Mathematics
Sergey Gorovoy, В. И. Коренбаум, Alexandr Tagiltcev, А. Е. Костив, И. А. Почекутова, Alexei Borodin, Aleksey Vasilistov, Alexandr Krupenkov,
The objective is acoustic detection of submerged diver and monitoring his physiologic condition. A possibility to use diver's own respiratory noises for this aim is analyzed. Respiratory noises were recorded above trachea of submerged scuba diver and in the water layer of shallow-water bay. Both signals contain quasi-periodic components induced by amplitude modulation of wideband respiratory noises with the rate of breathing maneuvers. These components are detected in water layer by means of energy ...
Tópico(s): Maritime Navigation and Safety
2014 - Acoustical Society of America | Proceedings of meetings on acoustics
O. V. Borodin, A. O. Ivanova, Alexandr Kostochka, Naeem N. Sheikh,
For an edge $xy$, let $M(xy)$ be the maximum of the degrees of $x$ and $y$. The {\em minimax degree} (or $M$-degree) of a graph $G$ is $M^*(G)=\min\{M(xy)| xy\in E(G)\}$. In order to get upper bounds on the game chromatic number of planar graphs, He, Hou, Lih, Shao, Wang, and Zhu showed that every planar graph $G$ without leaves and $4$-cycles has minimax degree at most $8$, which was improved by Borodin, Kostochka, Sheikh, and Yu to the sharp bound $7$. We show that every planar graph $G$ without leaves and $4$- ...
Tópico(s): Graph Labeling and Dimension Problems
2008 - Mathematical Society of the Republic of China (Taiwan) | Taiwanese Journal of Mathematics
Sergey Gorovoy, В. И. Коренбаум, A.M. Borodin, Alexandr Tagiltcev, А. Е. Костив, Anton Shiryaev, И. А. Почекутова,
The aim is an analysis of respiratory noises of diver equipped with a closed circuit breathing apparatus (rebreather). The noises were recorded in the shallow-water bay near the suit of the diver equipped with F.R.O.G.S. (Full Range Oxygen Gas System, http://www.aqualung.com) rebreather and at the distance of 3 m (in rest) by bottom located omnidirectional hydrophones. Energy receivers were used for detecting the noise signals in frequency bands of 30-300 Hz. Both hydrophone responses contained evident ...
Tópico(s): Marine animal studies overview
2016 - Acoustical Society of America | Proceedings of meetings on acoustics
Alexandr Lun-Fu, V. I. Borodin, M. A. Bubenchikov, Alexey M. Bubenchikov, D. V. Mamontov,
The manuscript presents a trajectory method for describing the rotations of surface crystals such as fullerenes, nanotubes, and nanotori. This method does not require the implementation of successive rotations of the considered molecular structures around the axes of the selected basis. Therefore, it is free from the shortcomings of the approaches of Euler and Hamilton. On its basis, an efficient algorithm for calculating the motions of a magneto-susceptible fullerene in an alternating magnetic ...
Tópico(s): Advanced Theoretical and Applied Studies in Material Sciences and Geometry
2022 - Multidisciplinary Digital Publishing Institute | Crystals
Kousha Etessami, Dieter van Melkebeek, Seth Pettie, John Watrous, Salil Vadhan,
... by the program committee, consisting of Ittai Abraham, Alexandr Andoni, Avrim Blum, Allan Borodin, Kousha Etessami, Lisa Fleischer, Venkatesan Guruswami, David Kempe, ...
Tópico(s): Optimization and Search Problems
2012 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing