| 1. |
- Asratian, Armen, 1951-
(författare)
-
Every 3-connected, locally connected, claw-free graph is Hamilton-connected
- 1996
-
Ingår i: Journal of Graph Theory. - : John Wiley & Sons. - 0364-9024 .- 1097-0118. ; 23:2, s. 191-201
-
Tidskriftsartikel (refereegranskat)abstract
- A graph G is locally connected if the subgraph induced by the neighbourhood of each vertex is connected. We prove that a locally connected graph G of order p ≥ 4, containing no induced subgraph isomorphic to K1,3, is Hamilton-connected if and only if G is 3-connected. © 1996 John Wiley & Sons, Inc.
|
|
| 2. |
- Asratian, Armen, et al.
(författare)
-
Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs
- 2009
-
Ingår i: Journal of Graph Theory. - : Wiley Periodicals Inc.. - 0364-9024 .- 1097-0118. ; 61:2, s. 88-97
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 3. |
- Asratian, Armen S., 1951-, et al.
(författare)
-
A characterization of panconnected graphs satisfying a local ore-type condition
- 1996
-
Ingår i: Journal of Graph Theory. - : Wiley Subscription Services, Inc., A Wiley Company. - 0364-9024 .- 1097-0118. ; 22:2, s. 95-103
-
Tidskriftsartikel (refereegranskat)abstract
- It is well known that a graph G of order p ≥ 3 is Hamilton-connected if d(u) + d(v) ≥ p + 1 for each pair of nonadjacent vertices u and v. In this paper we consider connected graphs G of order at least 3 for which d(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| + 1 for any path uwv with uv ∉ E(G), where N(x) denote the neighborhood of a vertex x. We prove that a graph G satisfying this condition has the following properties: (a) For each pair of nonadjacent vertices x, y of G and for each integer k, d(x, y) ≤ k ≤ |V(G)| − 1, there is an x − y path of length k. (b) For each edge xy of G and for each integer k (excepting maybe one k η 3,4) there is a cycle of length k containing xy.Consequently G is panconnected (and also edge pancyclic) if and only if each edge of G belongs to a triangle and a quadrangle.Our results imply some results of Williamson, Faudree, and Schelp. © 1996 John Wiley & Sons, Inc.
|
|
| 4. |
- Asratian, Armen S., 1951-, et al.
(författare)
-
On graphs satisfying a local ore-type condition
- 1996
-
Ingår i: Journal of Graph Theory. - : Wiley Subscription Services, Inc., A Wiley Company. - 0364-9024 .- 1097-0118. ; 21:1, s. 1-10
-
Tidskriftsartikel (refereegranskat)abstract
- {For an integer i, a graph is called an Li-graph if, for each triple of vertices u, v, w with d(u, v) = 2 and w (element of) N(u) (intersection) N(v), d(u) + d(v) ≥ | N(u) (union) N(v) (union) N(w)| —i. Asratian and Khachatrian proved that connected Lo-graphs of order at least 3 are hamiltonian, thus improving Ore’s Theorem. All K1,3-free graphs are L1-graphs, whence recognizing hamiltonian L1-graphs is an NP-complete problem. The following results about L1-graphs, unifying known results of Ore-type and known results on K1,3-free graphs, are obtained. Set K = lcub;G|Kp,p+1 (contained within) G (contained within) KpV Kp+1 for some ρ ≥ }(vdenotesjoin
|
|
| 5. |
- Asratian, Armen, et al.
(författare)
-
Solution of Vizings Problem on Interchanges for the case of Graphs with Maximum Degree 4 and Related Results
- 2016
-
Ingår i: Journal of Graph Theory. - : WILEY-BLACKWELL. - 0364-9024 .- 1097-0118. ; 82:4, s. 350-373
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 6. |
- Asratian, Armen, et al.
(författare)
-
Some results on cyclic interval edge colorings of graphs
- 2018
-
Ingår i: Journal of Graph Theory. - : WILEY. - 0364-9024 .- 1097-0118. ; 87:2, s. 239-252
-
Tidskriftsartikel (refereegranskat)abstract
- A proper edge coloring of a graph G with colors 1,2,,t is called a cyclic interval t-coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. We prove that a bipartite graph G of even maximum degree (G)4 admits a cyclic interval (G)-coloring if for every vertex v the degree dG(v) satisfies either dG(v)(G)-2 or dG(v)2. We also prove that every Eulerian bipartite graph G with maximum degree at most eight has a cyclic interval coloring. Some results are obtained for (a,b)-biregular graphs, that is, bipartite graphs with the vertices in one part all having degree a and the vertices in the other part all having degree b; it has been conjectured that all these have cyclic interval colorings. We show that all (4, 7)-biregular graphs as well as all (2r-2,2r)-biregular (r2) graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this proves a conjecture of Petrosyan and Mkhitaryan.
|
|
| 7. |
- Casselgren, Carl Johan, 1982-
(författare)
-
Brooks' theorem with forbidden colors
- 2024
-
Ingår i: Journal of Graph Theory. - : WILEY. - 0364-9024 .- 1097-0118. ; 105:3, s. 373-385
-
Tidskriftsartikel (refereegranskat)abstract
- We consider extensions of Brooks' classic theorem on vertex coloring where some colors cannot be used on certain vertices. In particular we prove that if G is a connected graph with maximum degree Delta(G) >= 4 that is not a complete graph and P subset of V (G) is a set of vertices where either (i) at most Delta(G) - 2 colors are forbidden for every vertex in P, and any two vertices of P are at distance at least 4, or (ii) at most Delta(G) - 3 colors are forbidden for every vertex in P, and any two vertices of P are at distance at least 3, then there is a proper Delta(G)-coloring of G respecting these constraints. In fact, we shall prove that these results hold in the more general setting of list colorings. These results are sharp.
|
|
| 8. |
- Casselgren, Carl Johan, et al.
(författare)
-
Edge precoloring extension of hypercubes
- 2020
-
Ingår i: Journal of Graph Theory. - : John Wiley & Sons. - 0364-9024 .- 1097-0118. ; 95:3, s. 410-444
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of extending partial edge colorings of hypercubes. In particular, we obtain an analogue of the positive solution to the famous Evans' conjecture on completing partial Latin squares by proving that every proper partial edge coloring of at most d − 1 edges of the d‐dimensional hypercube Qd can be extended to a proper d‐edge coloring of Qd. Additionally, we characterize which partial edge colorings of Qd with precisely d precolored edges are extendable to proper d‐edge colorings of Qd.
|
|
| 9. |
- Casselgren, Carl Johan, et al.
(författare)
-
On Interval Edge Colorings of Biregular Bipartite Graphs With Small Vertex Degrees
- 2015
-
Ingår i: Journal of Graph Theory. - : Wiley: 12 months. - 0364-9024 .- 1097-0118. ; 80:2, s. 83-97
-
Tidskriftsartikel (refereegranskat)abstract
- A proper edge coloring of a graph with colors 1, 2, 3, ... is called an interval coloring if the colors on the edges incident to each vertex form an interval of integers. A bipartite graph is (a,b)-biregular if every vertex in one part has degree a and every vertex in the other part has degree b. It has been conjectured that all such graphs have interval colorings. We prove that all (3, 6)-biregular graphs have interval colorings and that all (3, 9)-biregular graphs having a cubic subgraph covering all vertices of degree 9 admit interval colorings. Moreover, we prove that slightly weaker versions of the conjecture hold for (3, 5)-biregular, (4, 6)-biregular, and (4, 8)-biregular graphs. All our proofs are constructive and yield polynomial time algorithms for constructing the required colorings. (C) 2014 Wiley Periodicals, Inc.
|
|
| 10. |
- Falgas-Ravry, Victor, et al.
(författare)
-
Full subgraphs
- 2018
-
Ingår i: Journal of Graph Theory. - : Wiley. - 0364-9024 .- 1097-0118. ; 88:3, s. 411-427
-
Tidskriftsartikel (refereegranskat)
|
|
