Wiley: Journal of Graph Theory: Table of Contents
Table of Contents for Journal of Graph Theory. List of articles from both the latest and EarlyView issues.
https://onlinelibrary.wiley.com/loi/10970118?af=R
Wiley: Journal of Graph Theory: Table of Contents
Wiley
en-US
Journal of Graph Theory
Journal of Graph Theory
http://www.atypon.com/images/atypon_logo_small.gif
https://onlinelibrary.wiley.com/loi/10970118?af=R
Nowhere‐zero 3‐flow and ‐connectedness in graphs with four edge‐disjoint spanning trees
Abstract
Given a zero‐sum function with , an orientation D of G with in for every vertex is called a β‐orientation. A graph G is ‐connected if G admits a β‐orientation for every zero‐sum function β. Jaeger et al. conjectured that every 5‐edge‐connected graph is ‐connected. A graph is ‐extendable at vertex v if any preorientation at v can be extended to a β‐orientation of G for any zero‐sum function β. We observe that if every 5‐edge‐connected essentially 6‐edge‐connected graph is ‐extendable at any degree five vertex, then the above‐mentioned conjecture by Jaeger et al. holds as well. Furthermore, applying the partial flow extension method of Thomassen and of Lovász et al., we prove that every graph with at least four edge‐disjoint spanning trees is ‐connected. Consequently, every 5‐edge‐connected essentially 23‐edge‐connected graph is ‐extendable at any degree five vertex.
MiaomiaoHan
,
Hong‐JianLai
,
JiaaoLi
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/XAUIXqazskU/jgt.22231
Volume 88, Issue 4, Page 577-591, August 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 4, Page 577-591, August 2018. <br/>
Nowhere‐zero 3‐flow and ‐connectedness in graphs with four edge‐disjoint spanning trees
doi:10.1002/jgt.22231
Journal of Graph Theory
2017-12-14T08:00:00Z
Journal of Graph Theory
88
4
2017-12-14T08:00:00Z
2017-12-14T08:00:00Z
10.1002/jgt.22231
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22231?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22231?af=R
Cycles with two blocks in k‐chromatic digraphs
Abstract
Let k and ℓ be positive integers. A cycle with two blocks is a digraph obtained by an orientation of an undirected cycle, which consists of two internally (vertex) disjoint paths of lengths at least k and ℓ, respectively, from a vertex to another one. A problem of Addario‐Berry, Havet and Thomassé [J. Combin. Theory Ser. B 97 (2007), 620–626] asked if, given positive integers k and ℓ such that , any strongly connected digraph D containing no has chromatic number at most . In this article, we show that such digraph D has chromatic number at most , improving the previous upper bound of Cohen et al. [Subdivisions of oriented cycles in digraphs with large chromatic number, to appear]. We also show that if in addition D is Hamiltonian, then its underlying simple graph is ‐degenerate and thus the chromatic number of D is at most , which is tight.
RingiKim
,
Seog‐JinKim
,
JieMa
,
BoramPark
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/-h3658sF65Q/jgt.22232
Volume 88, Issue 4, Page 592-605, August 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 4, Page 592-605, August 2018. <br/>
Cycles with two blocks in k‐chromatic digraphs
doi:10.1002/jgt.22232
Journal of Graph Theory
2017-12-12T08:00:00Z
Journal of Graph Theory
88
4
2017-12-12T08:00:00Z
2017-12-12T08:00:00Z
10.1002/jgt.22232
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22232?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22232?af=R
Orientations of graphs with uncountable chromatic number
Abstract
Motivated by an old conjecture of P. Erdős and V. Neumann‐Lara, our aim is to investigate digraphs with uncountable dichromatic number and orientations of undirected graphs with uncountable chromatic number. A graph has uncountable chromatic number if its vertices cannot be covered by countably many independent sets, and a digraph has uncountable dichromatic number if its vertices cannot be covered by countably many acyclic sets. We prove that, consistently, there are digraphs with uncountable dichromatic number and arbitrarily large digirth; this is in surprising contrast with the undirected case: any graph with uncountable chromatic number contains a 4‐cycle. Next, we prove that several well‐known graphs (uncountable complete graphs, certain comparability graphs, and shift graphs) admit orientations with uncountable dichromatic number in ZFC. However, we show that the statement “every graph G of size and chromatic number ω1 has an orientation D with uncountable dichromatic number” is independent of ZFC. We end the article with several open problems.
Dániel T.Soukup
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/sje56gsgbSA/jgt.22233
Volume 88, Issue 4, Page 606-630, August 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 4, Page 606-630, August 2018. <br/>
Orientations of graphs with uncountable chromatic number
doi:10.1002/jgt.22233
Journal of Graph Theory
2017-12-26T08:00:00Z
Journal of Graph Theory
88
4
2017-12-26T08:00:00Z
2017-12-26T08:00:00Z
10.1002/jgt.22233
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22233?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22233?af=R
Decomposing planar cubic graphs
Abstract
The 3‐Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2‐regular subgraph and a matching. We show that this conjecture holds for the class of connected plane cubic graphs.
ArthurHoffmann‐Ostenhof
,
TomášKaiser
,
KentaOzeki
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/uvodI12epzg/jgt.22234
Volume 88, Issue 4, Page 631-640, August 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 4, Page 631-640, August 2018. <br/>
Decomposing planar cubic graphs
doi:10.1002/jgt.22234
Journal of Graph Theory
2018-01-10T08:00:00Z
Journal of Graph Theory
88
4
2018-01-10T08:00:00Z
2018-01-10T08:00:00Z
10.1002/jgt.22234
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22234?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22234?af=R
Every graph occurs as an induced subgraph of some hypohamiltonian graph
Abstract
We prove the titular statement. This settles a problem of Chvátal from 1973 and encompasses earlier results of Thomassen, who showed it for K3, and Collier and Schmeichel, who proved it for bipartite graphs. We also show that for every outerplanar graph there exists a planar hypohamiltonian graph containing it as an induced subgraph.
Carol T.Zamfirescu
,
Tudor I.Zamfirescu
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/8dsZ98L8h5o/jgt.22228
Volume 88, Issue 4, Page 551-557, August 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 4, Page 551-557, August 2018. <br/>
Every graph occurs as an induced subgraph of some hypohamiltonian graph
doi:10.1002/jgt.22228
Journal of Graph Theory
2017-12-11T08:00:00Z
Journal of Graph Theory
88
4
2017-12-11T08:00:00Z
2017-12-11T08:00:00Z
10.1002/jgt.22228
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22228?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22228?af=R
Multigraphs without large bonds are wqo by contraction
Abstract
We show that the class of multigraphs with at most p connected components and bonds of size at most k is well‐quasi‐ordered by edge contraction for all positive integers . (A bond is a minimal nonempty edge cut.) We also characterize canonical antichains for this relation.
MarcinKamiński
,
Jean‐FlorentRaymond
,
ThéophileTrunck
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/juhbb4Qz9ys/jgt.22229
Volume 88, Issue 4, Page 558-565, August 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 4, Page 558-565, August 2018. <br/>
Multigraphs without large bonds are wqo by contraction
doi:10.1002/jgt.22229
Journal of Graph Theory
2017-12-05T08:00:00Z
Journal of Graph Theory
88
4
2017-12-05T08:00:00Z
2017-12-05T08:00:00Z
10.1002/jgt.22229
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22229?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22229?af=R
Star chromatic index of subcubic multigraphs
Abstract
The star chromatic index of a multigraph G, denoted , is the minimum number of colors needed to properly color the edges of G such that no path or cycle of length four is bicolored. A multigraph G is star k‐edge‐colorable if . Dvořák, Mohar, and Šámal [Star chromatic index, J. Graph Theory 72 (2013), 313–326] proved that every subcubic multigraph is star 7‐edge‐colorable. They conjectured in the same article that every subcubic multigraph should be star 6‐edge‐colorable. In this article, we first prove that it is NP‐complete to determine whether for an arbitrary graph G. This answers a question of Mohar. We then establish some structure results on subcubic multigraphs G with such that but for any , where . We finally apply the structure results, along with a simple discharging method, to prove that every subcubic multigraph G is star 6‐edge‐colorable if , and star 5‐edge‐colorable if , respectively, where is the maximum average degree of a multigraph G. This partially confirms the conjecture of Dvořák, Mohar, and Šámal.
HuiLei
,
YongtangShi
,
Zi‐XiaSong
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/gPwYs-1tuM0/jgt.22230
Volume 88, Issue 4, Page 566-576, August 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 4, Page 566-576, August 2018. <br/>
Star chromatic index of subcubic multigraphs
doi:10.1002/jgt.22230
Journal of Graph Theory
2017-12-08T08:00:00Z
Journal of Graph Theory
88
4
2017-12-08T08:00:00Z
2017-12-08T08:00:00Z
10.1002/jgt.22230
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22230?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22230?af=R
Issue Information
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/q67Jz2vyWfk/jgt.22197
Volume 88, Issue 4, Page 547-549, August 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 4, Page 547-549, August 2018. <br/>
Issue Information
doi:10.1002/jgt.22197
Journal of Graph Theory
2018-06-14T05:06:33Z
Journal of Graph Theory
88
4
2018-06-14T05:06:33Z
2018-06-14T05:06:33Z
10.1002/jgt.22197
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22197?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22197?af=R
Extensions of a theorem of Erdős on nonhamiltonian graphs
Abstract
Let be integers with , and set . Erdős proved that when , each n‐vertex nonhamiltonian graph G with minimum degree has at most edges. He also provides a sharpness example for all such pairs . Previously, we showed a stability version of this result: for n large enough, every nonhamiltonian graph G on n vertices with and more than edges is a subgraph of . In this article, we show that not only does the graph maximize the number of edges among nonhamiltonian graphs with n vertices and minimum degree at least d, but in fact it maximizes the number of copies of any fixed graph F when n is sufficiently large in comparison with d and . We also show a stronger stability theorem, that is, we classify all nonhamiltonian n‐vertex graphs with and more than edges. We show this by proving a more general theorem: we describe all such graphs with more than copies of for any k.
ZoltánFüredi
,
AlexandrKostochka
,
RuthLuo
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/PGjmKyk68VI/jgt.22246
]]>
Journal of Graph Theory, EarlyView. <br/>
Extensions of a theorem of Erdős on nonhamiltonian graphs
doi:10.1002/jgt.22246
Journal of Graph Theory
2018-02-09T08:00:00Z
Journal of Graph Theory
2018-02-09T08:00:00Z
2018-02-09T08:00:00Z
10.1002/jgt.22246
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22246?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22246?af=R
Circuit covers of cubic signed graphs
Abstract
A signed graph, denoted by , is a graph G associated with a mapping . A cycle of is a connected 2‐regular subgraph. A cycle C is positive if it has an even number of negative edges, and negative otherwise. A signed‐circuit of a signed graph is a positive cycle or a barbell consisting of two edge‐disjoint negative cycles joined by a path. The definition of a signed‐circuit of signed graph comes from the signed‐graphic matroid. A signed‐circuit cover of is a family of signed‐circuits covering all edges of . A signed‐circuit cover with the smallest total length is called a shortest signed‐circuit cover of and its length is denoted by . Bouchet proved that a signed graph has a signed‐circuit cover if and only if it is flow‐admissible (i.e., has a nowhere‐zero integer flow). In this article, we show that a 3‐connected flow‐admissible signed graph does not necessarily have a signed‐circuit double cover. For shortest signed‐circuit cover of 2‐edge‐connected cubic signed graphs , we show that if it is flow‐admissible.
YezhouWu
,
DongYe
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/f3xjkicjI10/jgt.22238
]]>
Journal of Graph Theory, EarlyView. <br/>
Circuit covers of cubic signed graphs
doi:10.1002/jgt.22238
Journal of Graph Theory
2018-02-01T08:00:00Z
Journal of Graph Theory
2018-02-01T08:00:00Z
2018-02-01T08:00:00Z
10.1002/jgt.22238
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22238?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22238?af=R
Separation dimension and sparsity
Abstract
The separation dimension of a hypergraph G is the smallest natural number k for which the vertices of G can be embedded in so that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the cardinality of a smallest family of total orders of , such that for any two disjoint edges of G, there exists at least one total order in in which all the vertices in one edge precede those in the other. Separation dimension is a monotone parameter; adding more edges cannot reduce the separation dimension of a hypergraph. In this article, we discuss the influence of separation dimension and edge‐density of a graph on one another. On one hand, we show that the maximum separation dimension of a k‐degenerate graph on n vertices is and that there exists a family of 2‐degenerate graphs with separation dimension . On the other hand, we show that graphs with bounded separation dimension cannot be very dense. Quantitatively, we prove that n‐vertex graphs with separation dimension s have at most edges. We do not believe that this bound is optimal and give a question and a remark on the optimal bound.
NogaAlon
,
ManuBasavaraju
,
L. SunilChandran
,
RogersMathew
,
DeepakRajendraprasad
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/lMc9KbqxA2w/jgt.22236
]]>
Journal of Graph Theory, EarlyView. <br/>
Separation dimension and sparsity
doi:10.1002/jgt.22236
Journal of Graph Theory
2018-02-01T08:00:00Z
Journal of Graph Theory
2018-02-01T08:00:00Z
2018-02-01T08:00:00Z
10.1002/jgt.22236
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22236?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22236?af=R
Graphs in which some and every maximum matching is uniquely restricted
Abstract
A matching M in a graph G is uniquely restricted if there is no matching in G that is distinct from M but covers the same vertices as M. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely restricted. Both our characterizations lead to efficient recognition algorithms for the corresponding graphs.
Lucia DraquePenso
,
DieterRautenbach
,
Uévertondos Santos Souza
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/l_lGIVSi4xA/jgt.22239
]]>
Journal of Graph Theory, EarlyView. <br/>
Graphs in which some and every maximum matching is uniquely restricted
doi:10.1002/jgt.22239
Journal of Graph Theory
2018-02-02T08:00:00Z
Journal of Graph Theory
2018-02-02T08:00:00Z
2018-02-02T08:00:00Z
10.1002/jgt.22239
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22239?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22239?af=R
Abstract
We improve the upper bound on the Ramsey number R(5, 5) from to . We also complete the catalog of extremal graphs for R(4, 5).
VigleikAngeltveit
,
Brendan D.McKay
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/Km9Kg13azyI/jgt.22235
]]>
Journal of Graph Theory, EarlyView. <br/>
doi:10.1002/jgt.22235
Journal of Graph Theory
2018-02-05T08:00:00Z
Journal of Graph Theory
2018-02-05T08:00:00Z
2018-02-05T08:00:00Z
10.1002/jgt.22235
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22235?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22235?af=R
The width of quadrangulations of the projective plane
Abstract
We show that every 4‐chromatic graph on n vertices, with no two vertex‐disjoint odd cycles, has an odd cycle of length at most . Let G be a nonbipartite quadrangulation of the projective plane on n vertices. Our result immediately implies that G has edge‐width at most , which is sharp for infinitely many values of n. We also show that G has face‐width (equivalently, contains an odd cycle transversal of cardinality) at most , which is a constant away from the optimal; we prove a lower bound of . Finally, we show that G has an odd cycle transversal of size at most inducing a single edge, where Δ is the maximum degree. This last result partially answers a question of Nakamoto and Ozeki.
LouisEsperet
,
MatějStehlík
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/zaY7W9IPECQ/jgt.22241
]]>
Journal of Graph Theory, EarlyView. <br/>
The width of quadrangulations of the projective plane
doi:10.1002/jgt.22241
Journal of Graph Theory
2018-02-06T08:00:00Z
Journal of Graph Theory
2018-02-06T08:00:00Z
2018-02-06T08:00:00Z
10.1002/jgt.22241
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22241?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22241?af=R
Supereulerian bipartite digraphs
Abstract
A digraph D is supereulerian if D has a spanning closed ditrail. Bang‐Jensen and Thomassé conjectured that if the arc‐strong connectivity of a digraph D is not less than the independence number , then D is supereulerian. A digraph is bipartite if its underlying graph is bipartite. Let be the size of a maximum matching of D. We prove that if D is a bipartite digraph satisfying , then D is supereulerian. Consequently, every bipartite digraph D satisfying is supereulerian. The bound of our main result is best possible.
XindongZhang
,
JuanLiu
,
LanWang
,
Hong‐JianLai
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/QXa4rlITFP0/jgt.22240
]]>
Journal of Graph Theory, EarlyView. <br/>
Supereulerian bipartite digraphs
doi:10.1002/jgt.22240
Journal of Graph Theory
2018-02-06T08:00:00Z
Journal of Graph Theory
2018-02-06T08:00:00Z
2018-02-06T08:00:00Z
10.1002/jgt.22240
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22240?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22240?af=R
Extremal graphs for the k‐flower
Abstract
The Turán number of a graph H, , is the maximum number of edges in any graph of order n that does not contain an H as a subgraph. A graph on vertices consisting of k triangles that intersect in exactly one common vertex is called a k‐fan, and a graph consisting of k cycles that intersect in exactly one common vertex is called a k‐flower. In this article, we determine the Turán number of any k‐flower containing at least one odd cycle and characterize all extremal graphs provided n is sufficiently large. Erdős, Füredi, Gould, and Gunderson determined the Turán number for the k‐fan. Our result is a generalization of their result. The addition aim of this article is to draw attention to a powerful tool, the so‐called progressive induction lemma of Simonovits.
Long‐TuYuan
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/slumnN27gGg/jgt.22237
]]>
Journal of Graph Theory, EarlyView. <br/>
Extremal graphs for the k‐flower
doi:10.1002/jgt.22237
Journal of Graph Theory
2018-02-06T08:00:00Z
Journal of Graph Theory
2018-02-06T08:00:00Z
2018-02-06T08:00:00Z
10.1002/jgt.22237
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22237?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22237?af=R
A constructive characterisation of circuits in the simple (2,1)‐sparse matroid
Abstract
A simple graph is a (2, 1)‐circuit if and for every proper subgraph H of G. Motivated, in part, by ongoing work to understand unique realisations of graphs on surfaces, we derive a constructive characterisation of (2, 1)‐circuits. The characterisation uses the well‐known 1‐extension and X‐replacement operations as well as several summation moves to glue together (2, 1)‐circuits over small cutsets.
Thomas A.McCourt
,
AnthonyNixon
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/QjB1wyz3XCA/jgt.22245
]]>
Journal of Graph Theory, EarlyView. <br/>
A constructive characterisation of circuits in the simple (2,1)‐sparse matroid
doi:10.1002/jgt.22245
Journal of Graph Theory
2018-02-06T08:00:00Z
Journal of Graph Theory
2018-02-06T08:00:00Z
2018-02-06T08:00:00Z
10.1002/jgt.22245
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22245?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22245?af=R
Tight lower bounds on the matching number in a graph with given maximum degree
Abstract
Let . We prove the following three bounds for the matching number, , of a graph, G, of order n size m and maximum degree at most k.
If k is odd, then .
If k is even, then .
If k is even, then .
In this article, we actually prove a slight strengthening of the above for which the bounds are tight for essentially all densities of graphs.
The above three bounds are in fact powerful enough to give a complete description of the set of pairs of real numbers with the following property. There exists a constant K such that for every connected graph G with maximum degree at most k, where n and m denote the number of vertices and the number of edges, respectively, in G. We show that is a convex set. Further, if k is odd, then is the intersection of two closed half‐spaces, and there is exactly one extreme point of , while if k is even, then is the intersection of three closed half‐spaces, and there are precisely two extreme points of .
Michael A.Henning
,
AndersYeo
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/ToTKIDmDsTY/jgt.22244
]]>
Journal of Graph Theory, EarlyView. <br/>
Tight lower bounds on the matching number in a graph with given maximum degree
doi:10.1002/jgt.22244
Journal of Graph Theory
2018-02-06T08:00:00Z
Journal of Graph Theory
2018-02-06T08:00:00Z
2018-02-06T08:00:00Z
10.1002/jgt.22244
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22244?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22244?af=R
More on foxes
Abstract
An edge in a k‐connected graph G is called k‐contractible if the graph obtained from G by contracting e is k‐connected. Generalizing earlier results on 3‐contractible edges in spanning trees of 3‐connected graphs, we prove that (except for the graphs if ) (a) every spanning tree of a k‐connected triangle free graph has two k‐contractible edges, (b) every spanning tree of a k‐connected graph of minimum degree at least has two k‐contractible edges, (c) for , every DFS tree of a k‐connected graph of minimum degree at least has two k‐contractible edges, (d) every spanning tree of a cubic 3‐connected graph nonisomorphic to K4 has at least many 3‐contractible edges, and (e) every DFS tree of a 3‐connected graph nonisomorphic to K4, the prism, or the prism plus a single edge has two 3‐contractible edges. We also discuss in which sense these theorems are best possible.
MatthiasKriesell
,
Jens M.Schmidt
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/qY16b1NYtDE/jgt.22243
]]>
Journal of Graph Theory, EarlyView. <br/>
More on foxes
doi:10.1002/jgt.22243
Journal of Graph Theory
2018-02-08T08:00:00Z
Journal of Graph Theory
2018-02-08T08:00:00Z
2018-02-08T08:00:00Z
10.1002/jgt.22243
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22243?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22243?af=R
On homeomorphically irreducible spanning trees in cubic graphs
Abstract
A spanning tree without a vertex of degree two is called a HIST, which is an abbreviation for homeomorphically irreducible spanning tree. We provide a necessary condition for the existence of a HIST in a cubic graph. As one consequence, we answer affirmatively an open question on HISTs by Albertson, Berman, Hutchinson, and Thomassen. We also show several results on the existence of HISTs in plane and toroidal cubic graphs.
ArthurHoffmann‐Ostenhof
,
KentaNoguchi
,
KentaOzeki
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/ILJKEbX1KAE/jgt.22242
]]>
Journal of Graph Theory, EarlyView. <br/>
On homeomorphically irreducible spanning trees in cubic graphs
doi:10.1002/jgt.22242
Journal of Graph Theory
2018-02-19T08:00:00Z
Journal of Graph Theory
2018-02-19T08:00:00Z
2018-02-19T08:00:00Z
10.1002/jgt.22242
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22242?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22242?af=R
Nonseparating K4‐subdivisions in graphs of minimum degree at least 4
Abstract
We first prove that for every vertex x of a 4‐connected graph G, there exists a subgraph H in G isomorphic to a subdivision of the complete graph K4 on four vertices such that is connected and contains x. This implies an affirmative answer to a question of Kühnel whether every 4‐connected graph G contains a subdivision H of K4 as a subgraph such that is connected. The motor for our induction is a result of Fontet and Martinov stating that every 4‐connected graph can be reduced to a smaller one by contracting a single edge, unless the graph is the square of a cycle or the line graph of a cubic graph. It turns out that this is the only ingredient of the proof where 4‐connectedness is used. We then generalize our result to connected graphs of minimum degree at least 4 by developing the respective motor, a structure theorem for the class of simple connected graphs of minimum degree at least 4. A simple connected graph G of minimum degree 4 cannot be reduced to a smaller such graph by deleting a single edge or contracting a single edge and simplifying if and only if it is the square of a cycle or the edge disjoint union of copies of certain bricks as follows: Each brick is isomorphic to K3, K5, K2, 2, 2, , , or one the four graphs , , , obtained from K5 and K2, 2, 2 by deleting the edges of a triangle, or replacing a vertex x by two new vertices and adding four edges to the endpoints of two disjoint edges of its former neighborhood, respectively. Bricks isomorphic to K5 or K2, 2, 2 share exactly one vertex with the other bricks of the decomposition, vertices of degree 4 in any other brick are not contained in any further brick of the decomposition, and the vertices of a brick isomorphic to K3 must have degree 4 in G and have pairwise no common neighbors outside that brick.
MatthiasKriesell
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/zsnvhTURL6c/jgt.22247
]]>
Journal of Graph Theory, EarlyView. <br/>
Nonseparating K4‐subdivisions in graphs of minimum degree at least 4
doi:10.1002/jgt.22247
Journal of Graph Theory
2018-03-31T03:24:37Z
Journal of Graph Theory
2018-03-31T03:24:37Z
2018-03-31T03:24:37Z
10.1002/jgt.22247
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22247?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22247?af=R
Excluding pairs of tournaments
Abstract
The Erdős–Hajnal conjecture states that for every given undirected graph H there exists a constant such that every graph G that does not contain H as an induced subgraph contains a clique or a stable set of size at least . The conjecture is still open. Its equivalent directed version states that for every given tournament H there exists a constant such that every H‐free tournament T contains a transitive subtournament of order at least . In this article, we prove that for several pairs of tournaments, H1 and H2, there exists a constant such that every ‐free tournament T contains a transitive subtournament of size at least . In particular, we prove that for several tournaments H, there exists a constant such that every ‐free tournament T, where stands for the complement of H, has a transitive subtournament of size at least . To the best of our knowledge these are first nontrivial results of this type.
KrzysztofChoromanski
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/AnaK5xzsJk4/jgt.22250
]]>
Journal of Graph Theory, EarlyView. <br/>
Excluding pairs of tournaments
doi:10.1002/jgt.22250
Journal of Graph Theory
2018-04-10T10:43:39Z
Journal of Graph Theory
2018-04-10T10:43:39Z
2018-04-10T10:43:39Z
10.1002/jgt.22250
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22250?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22250?af=R
χ‐bounded families of oriented graphs
Abstract
A famous conjecture of Gyárfás and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star S and integer k, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size k or it contains S as an induced subgraph. As an evidence, we prove that for any oriented star S, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order 3 or S as an induced subdigraph. We then study for which sets of orientations of P4 (the path on four vertices) similar statements hold. We establish some positive and negative results.
P.Aboulker
,
J.Bang‐Jensen
,
N.Bousquet
,
P.Charbit
,
F.Havet
,
F.Maffray
,
J.Zamora
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/mWKrs8cx8L4/jgt.22252
]]>
Journal of Graph Theory, EarlyView. <br/>
χ‐bounded families of oriented graphs
doi:10.1002/jgt.22252
Journal of Graph Theory
2018-04-10T11:38:49Z
Journal of Graph Theory
2018-04-10T11:38:49Z
2018-04-10T11:38:49Z
10.1002/jgt.22252
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22252?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22252?af=R
Coloring (gem, co‐gem)‐free graphs
Abstract
A gem is a graph that consists of a path on four vertices plus a vertex adjacent to all four vertices of the path. A co‐gem is the complement of a gem. We prove that every (gem, co‐gem)‐free graph G satisfies the inequality (a special case of a conjecture of Gyárfás) and the inequality (a special case of a conjecture of Reed). Moreover, we give an ‐time algorithm that computes the chromatic number of any (gem, co‐gem)‐free graph with n vertices, while the existing algorithm in the literature takes .
T.Karthick
,
FrédéricMaffray
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/gv2tKU5Ic6M/jgt.22251
]]>
Journal of Graph Theory, EarlyView. <br/>
Coloring (gem, co‐gem)‐free graphs
doi:10.1002/jgt.22251
Journal of Graph Theory
2018-04-12T11:09:49Z
Journal of Graph Theory
2018-04-12T11:09:49Z
2018-04-12T11:09:49Z
10.1002/jgt.22251
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22251?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22251?af=R
No optimal 1‐planar graph triangulates any nonorientable closed surface
Abstract
Suzuki [Discrete Math. 310 (2010), 6–11] proved that for any orientable closed surface F2 other than the sphere, there exists an optimal 1‐planar graph which can be embedded on F2 as a triangulation. However, for nonorientable closed surfaces, the existence of such graphs is unknown. In this article, we prove that no optimal 1‐planar graph triangulates a nonorientable closed surface.
TakuNagasawa
,
KentaNoguchi
,
YusukeSuzuki
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/t4iOOpzzBJY/jgt.22255
]]>
Journal of Graph Theory, EarlyView. <br/>
No optimal 1‐planar graph triangulates any nonorientable closed surface
doi:10.1002/jgt.22255
Journal of Graph Theory
2018-04-20T06:33:10Z
Journal of Graph Theory
2018-04-20T06:33:10Z
2018-04-20T06:33:10Z
10.1002/jgt.22255
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22255?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22255?af=R
Degree sum and vertex dominating paths
Abstract
A vertex dominating path in a graph is a path P such that every vertex outside P has a neighbor on P. In 1988 H. Broersma [5] stated a result implying that every n‐vertex k‐connected graph G such that contains a vertex dominating path. We provide a short, self‐contained proof of this result and further show that every n‐vertex k‐connected graph such that contains a vertex dominating path of length at most , where T is a minimum dominating set of vertices. An immediate corollary of this result is that every such graph contains a vertex dominating path with length bounded above by a logarithmic function of the order of the graph. To derive this result, we prove that every n‐vertex k‐connected graph with contains a path of length at most , through any set of T vertices where .
JillFaudree
,
Ralph J.Faudree
,
Ronald J.Gould
,
PaulHorn
,
Michael S.Jacobson
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/U1B20D4eT0I/jgt.22249
]]>
Journal of Graph Theory, EarlyView. <br/>
Degree sum and vertex dominating paths
doi:10.1002/jgt.22249
Journal of Graph Theory
2018-04-20T06:34:46Z
Journal of Graph Theory
2018-04-20T06:34:46Z
2018-04-20T06:34:46Z
10.1002/jgt.22249
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22249?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22249?af=R
On minimum bisection and related cut problems in trees and tree‐like graphs
Abstract
Minimum bisection denotes the NP‐hard problem to partition the vertex set of a graph into two sets of equal sizes while minimizing the width of the bisection, which is defined as the number of edges between these two sets. It is intuitively clear that graphs with a somewhat linear structure are easy to bisect, and therefore our aim is to relate the minimum bisection width of a bounded‐degree graph G to a parameter that measures the similarity between G and a path. First, for trees, we use the diameter and show that the minimum bisection width of every tree T on n vertices satisfies . Second, we generalize this to arbitrary graphs with a given tree decomposition and give an upper bound on the minimum bisection width that depends on how close is to a path decomposition. Moreover, we show that a bisection satisfying our general bound can be computed in time proportional to the encoding length of the tree decomposition when the latter is provided as input.
Cristina G.Fernandes
,
Tina JanneSchmidt
,
AnuschTaraz
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/s1edo_qLRhQ/jgt.22248
]]>
Journal of Graph Theory, EarlyView. <br/>
On minimum bisection and related cut problems in trees and tree‐like graphs
doi:10.1002/jgt.22248
Journal of Graph Theory
2018-04-20T06:43:05Z
Journal of Graph Theory
2018-04-20T06:43:05Z
2018-04-20T06:43:05Z
10.1002/jgt.22248
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22248?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22248?af=R
On bipartite‐mixed graphs
Abstract
Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this article, we consider the case where such graphs are bipartite. As main results, we show that in this context the Moore‐like bound is attained in the case of diameter , and that bipartite‐mixed graphs of diameter do not exist.
CristinaDalfó
,
Miquel ÀngelFiol
,
NachoLópez
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/VzijjwgH7fo/jgt.22257
]]>
Journal of Graph Theory, EarlyView. <br/>
On bipartite‐mixed graphs
doi:10.1002/jgt.22257
Journal of Graph Theory
2018-04-24T10:28:52Z
Journal of Graph Theory
2018-04-24T10:28:52Z
2018-04-24T10:28:52Z
10.1002/jgt.22257
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22257?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22257?af=R
On the structure of (banner, odd hole)‐free graphs
Abstract
A hole is a chordless cycle with at least four vertices. A hole is odd if it has an odd number of vertices. A banner is a graph that consists of a hole on four vertices and a single vertex with precisely one neighbor on the hole. We prove that a (banner, odd hole)‐free graph is perfect, or does not contain a stable set on three vertices, or contains a homogeneous set. Using this structure result, we design a polynomial‐time algorithm for recognizing (banner, odd hole)‐free graphs. We also design polynomial‐time algorithms to find, for such a graph, a minimum coloring, and largest stable set. A graph G is perfectly divisible if every induced subgraph H of G contains a set X of vertices such that X meets all largest cliques of H, and X induces a perfect graph. The chromatic number of a perfectly divisible graph G is bounded by ω2 where ω denotes the number of vertices in a largest clique of G. We prove that (banner, odd hole)‐free graphs are perfectly divisible.
Chính T.Hoàng
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/vVA-RscWe0o/jgt.22258
]]>
Journal of Graph Theory, EarlyView. <br/>
On the structure of (banner, odd hole)‐free graphs
doi:10.1002/jgt.22258
Journal of Graph Theory
2018-04-25T07:09:02Z
Journal of Graph Theory
2018-04-25T07:09:02Z
2018-04-25T07:09:02Z
10.1002/jgt.22258
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22258?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22258?af=R
The 2‐surviving rate of planar graphs with average degree lower than
Abstract
Let G be any connected graph on n vertices, . Let k be any positive integer. Suppose that a fire breaks out at some vertex of G. Then, in each turn firefighters can protect at most k vertices of G not yet on fire; Next the fire spreads to all unprotected neighbors of burning vertices. The k‐surviving rate of G, denoted by , is the expected fraction of vertices that can be saved from the fire, provided that the starting vertex is chosen uniformly at random. In this note, it is shown that for any planar graph G with average degree , where , there is . In particular, the result implies a significant improvement of the bound for 2‐surviving rate for triangle‐free planar graphs (Esperet et al. ) and for planar graphs without 4‐cycles (Kong et al. ). The proof is done using the separator theorem for planar graphs.
PrzemysławGordinowicz
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/jGd0Phnr5Sc/jgt.22254
]]>
Journal of Graph Theory, EarlyView. <br/>
The 2‐surviving rate of planar graphs with average degree lower than
doi:10.1002/jgt.22254
Journal of Graph Theory
2018-04-28T05:15:00Z
Journal of Graph Theory
2018-04-28T05:15:00Z
2018-04-28T05:15:00Z
10.1002/jgt.22254
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22254?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22254?af=R
Subdivisions of oriented cycles in digraphs with large chromatic number
Abstract
An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle C, there are digraphs containing no subdivision of C (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that for any C a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of C. We prove a similar result for the antidirected cycle on four vertices (in which two vertices have out‐degree 2 and two vertices have in‐degree 2).
NathannCohen
,
FrédéricHavet
,
WilliamLochet
,
NicolasNisse
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/EYMrk95138o/jgt.22360
]]>
Journal of Graph Theory, EarlyView. <br/>
Subdivisions of oriented cycles in digraphs with large chromatic number
doi:10.1002/jgt.22360
Journal of Graph Theory
2018-04-30T05:12:36Z
Journal of Graph Theory
2018-04-30T05:12:36Z
2018-04-30T05:12:36Z
10.1002/jgt.22360
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22360?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22360?af=R
Size of the largest induced forest in subcubic graphs of girth at least four and five
Abstract
In this article, we address the maximum number of vertices of induced forests in subcubic graphs with girth at least four or five. We provide a unified approach to prove that every 2‐connected subcubic graph on n vertices and m edges with girth at least four or five, respectively, has an induced forest on at least or vertices, respectively, except for finitely many exceptional graphs. Our results improve a result of Liu and Zhao and are tight in the sense that the bounds are attained by infinitely many 2‐connected graphs. Equivalently, we prove that such graphs admit feedback vertex sets with size at most or , respectively. Those exceptional graphs will be explicitly constructed, and our result can be easily modified to drop the 2‐connectivity requirement.
TomKelly
,
Chun‐HungLiu
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/6PbGUtAd1WI/jgt.22361
]]>
Journal of Graph Theory, EarlyView. <br/>
Size of the largest induced forest in subcubic graphs of girth at least four and five
doi:10.1002/jgt.22361
Journal of Graph Theory
2018-04-30T07:00:00Z
Journal of Graph Theory
2018-04-30T07:00:00Z
2018-04-30T07:00:00Z
10.1002/jgt.22361
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22361?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22361?af=R
Subtrees of graphs
Abstract
We study a new graph invariant, the sequence of the number of k‐edge subtrees of a graph. We compute the mean subtree size for several classes of graphs, concentrating on complete graphs, complete bipartite graphs, and theta graphs, in particular. We prove that the ratio of spanning trees to all subtrees in approaches , and give a related formula for . We also connect the number of subtrees of that contain a given subtree to the hyperbinomial transform. For theta graphs, we find formulas for the mean subtree size (approximately ) and the mode (approximately ) of the unimodal sequence . The main tool is a subtree generating function.
Alex J.Chin
,
GaryGordon
,
Kellie J.MacPhee
,
CharlesVincent
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/Ej1gKU5QX8U/jgt.22359
]]>
Journal of Graph Theory, EarlyView. <br/>
Subtrees of graphs
doi:10.1002/jgt.22359
Journal of Graph Theory
2018-05-02T07:00:00Z
Journal of Graph Theory
2018-05-02T07:00:00Z
2018-05-02T07:00:00Z
10.1002/jgt.22359
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22359?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22359?af=R
Optimal‐size clique transversals in chordal graphs
Abstract
The following question was raised by Tuza in 1990 and Erdős et al. in 1992: if every edge of an n‐vertex chordal graph G is contained in a clique of size at least four, does G have a clique transversal, i.e. a set of vertices meeting all nontrivial maximal cliques, of size at most ? We prove that every such graph G has a clique transversal of size at most if , which is the best possible bound.
Jacob W.Cooper
,
AndrzejGrzesik
,
DanielKrál'
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/4zrFOaTGj_Q/jgt.22362
]]>
Journal of Graph Theory, EarlyView. <br/>
Optimal‐size clique transversals in chordal graphs
doi:10.1002/jgt.22362
Journal of Graph Theory
2018-05-03T05:33:34Z
Journal of Graph Theory
2018-05-03T05:33:34Z
2018-05-03T05:33:34Z
10.1002/jgt.22362
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22362?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22362?af=R
On the edge spectrum of saturated graphs for paths and stars
Abstract
For a given graph H, we say that a graph G on n vertices is H‐saturated if H is not a subgraph of G, but for any edge the graph contains a subgraph isomorphic to H. The set of all values m for which there exists an H‐saturated graph on n vertices and m edges is called the edge spectrum for H‐saturated graphs. In the present article, we study the edge spectrum for H‐saturated graphs when H is a path or a star. In particular, we show that the edge spectrum for star‐saturated graphs consists of all integers between the saturation number and extremal number, and the edge spectrum of path‐saturated graphs includes all integers from the saturation number to slightly below the extremal number, but in general will include gaps just below the extremal number. We also investigate the second largest ‐saturated graphs as well as some structural results about path‐saturated graphs that have edge counts close to the extremal number.
PaulBalister
,
AliDogan
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/AjDL_J2yC3g/jgt.22256
]]>
Journal of Graph Theory, EarlyView. <br/>
On the edge spectrum of saturated graphs for paths and stars
doi:10.1002/jgt.22256
Journal of Graph Theory
2018-05-02T07:00:00Z
Journal of Graph Theory
2018-05-02T07:00:00Z
2018-05-02T07:00:00Z
10.1002/jgt.22256
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22256?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22256?af=R
Decomposing C4‐free graphs under degree constraints
Abstract
A celebrated theorem of Stiebitz 13 asserts that any graph with minimum degree at least can be partitioned into two parts that induce two subgraphs with minimum degree at least s and t, respectively. This resolved a conjecture of Thomassen. In this article, we prove that for , if a graph G contains no cycle of length four and has minimum degree at least , then G can be partitioned into two parts that induce two subgraphs with minimum degree at least s and t, respectively. This improves the result of Diwan in 5, where he proved the same statement for graphs of girth at least five. Our proof also works for the case of variable functions, in which the bounds are sharp as showing by some polarity graphs.
JieMa
,
TianchiYang
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/rMVtTxy_N8A/jgt.22364
]]>
Journal of Graph Theory, EarlyView. <br/>
Decomposing C4‐free graphs under degree constraints
doi:10.1002/jgt.22364
Journal of Graph Theory
2018-06-07T09:59:08Z
Journal of Graph Theory
2018-06-07T09:59:08Z
2018-06-07T09:59:08Z
10.1002/jgt.22364
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22364?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22364?af=R
A tanglegram Kuratowski theorem
Abstract
A tanglegram consists of two rooted binary plane trees with the same number of leaves and a perfect matching between the two leaf sets. Tanglegrams are drawn with the leaves on two parallel lines, the trees on either side of the strip created by these lines, and the perfect matching inside the strip. If this can be done without any edges crossing, a tanglegram is called planar. We show that every nonplanar tanglegram contains one of two nonplanar 4‐leaf tanglegrams as an induced subtanglegram, which parallels Kuratowski's Theorem.
ÉvaCzabarka
,
László A.Székely
,
StephanWagner
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/_-U1jivKnn0/jgt.22370
]]>
Journal of Graph Theory, EarlyView. <br/>
A tanglegram Kuratowski theorem
doi:10.1002/jgt.22370
Journal of Graph Theory
2018-06-10T07:00:00Z
Journal of Graph Theory
2018-06-10T07:00:00Z
2018-06-10T07:00:00Z
10.1002/jgt.22370
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22370?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22370?af=R
Perfect divisibility and 2‐divisibility
Abstract
A graph G is said to be 2‐divisible if for all (nonempty) induced subgraphs H of G, can be partitioned into two sets such that and . (Here denotes the clique number of G, the number of vertices in a largest clique of G). A graph G is said to be perfectly divisible if for all induced subgraphs H of G, can be partitioned into two sets such that is perfect and . We prove that if a graph is ‐free, then it is 2‐divisible. We also prove that if a graph is bull‐free and either odd‐hole‐free or P5‐free, then it is perfectly divisible.
MariaChudnovsky
,
VaidySivaraman
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/emN7cypoKzs/jgt.22367
]]>
Journal of Graph Theory, EarlyView. <br/>
Perfect divisibility and 2‐divisibility
doi:10.1002/jgt.22367
Journal of Graph Theory
2018-06-10T07:00:00Z
Journal of Graph Theory
2018-06-10T07:00:00Z
2018-06-10T07:00:00Z
10.1002/jgt.22367
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22367?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22367?af=R
Bad news for chordal partitions
Abstract
Reed and Seymour [1998] asked whether every graph has a partition into induced connected nonempty bipartite subgraphs such that the quotient graph is chordal. If true, this would have significant ramifications for Hadwiger's Conjecture. We prove that the answer is “no.” In fact, we show that the answer is still “no” for several relaxations of the question.
AlexScott
,
PaulSeymour
,
David R.Wood
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/DWXjUl5Uk6o/jgt.22363
]]>
Journal of Graph Theory, EarlyView. <br/>
Bad news for chordal partitions
doi:10.1002/jgt.22363
Journal of Graph Theory
2018-06-13T02:44:36Z
Journal of Graph Theory
2018-06-13T02:44:36Z
2018-06-13T02:44:36Z
10.1002/jgt.22363
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22363?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22363?af=R
Antimagic orientations of even regular graphs
Abstract
A labeling of a digraph D with m arcs is a bijection from the set of arcs of D to . A labeling of D is antimagic if no two vertices in D have the same vertex‐sum, where the vertex‐sum of a vertex for a labeling is the sum of labels of all arcs entering u minus the sum of labels of all arcs leaving u. Motivated by the conjecture of Hartsfield and Ringel from 1990 on antimagic labelings of graphs, Hefetz, Mütze, and Schwartz [On antimagic directed graphs, J. Graph Theory 64 (2010) 219–232] initiated the study of antimagic labelings of digraphs, and conjectured that every connected graph admits an antimagic orientation, where an orientation D of a graph G is antimagic if D has an antimagic labeling. It remained unknown whether every disjoint union of cycles admits an antimagic orientation. In this article, we first answer this question in the positive by proving that every 2‐regular graph has an antimagic orientation. We then show that for any integer , every connected, 2d‐regular graph has an antimagic orientation. Our technique is new.
TongLi
,
Zi‐XiaSong
,
GuanghuiWang
,
DongleiYang
,
Cun‐QuanZhang
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/ezWNe2t1HkY/jgt.22366
]]>
Journal of Graph Theory, EarlyView. <br/>
Antimagic orientations of even regular graphs
doi:10.1002/jgt.22366
Journal of Graph Theory
2018-06-13T04:30:37Z
Journal of Graph Theory
2018-06-13T04:30:37Z
2018-06-13T04:30:37Z
10.1002/jgt.22366
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22366?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22366?af=R
Komlós's tiling theorem via graphon covers
Abstract
Komlós [Komlós: Tiling Turán Theorems, Combinatorica, 2000] determined the asymptotically optimal minimum‐degree condition for covering a given proportion of vertices of a host graph by vertex‐disjoint copies of a fixed graph H, thus essentially extending the Hajnal–Szemerédi theorem that deals with the case when H is a clique. We give a proof of a graphon version of Komlós's theorem. To prove this graphon version, and also to deduce from it the original statement about finite graphs, we use the machinery introduced in [Hladký, Hu, Piguet: Tilings in graphons, arXiv:1606.03113]. We further prove a stability version of Komlós's theorem.
JanHladký
,
PingHu
,
DianaPiguet
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/E05wB4CQF0o/jgt.22365
]]>
Journal of Graph Theory, EarlyView. <br/>
Komlós's tiling theorem via graphon covers
doi:10.1002/jgt.22365
Journal of Graph Theory
2018-06-13T05:36:03Z
Journal of Graph Theory
2018-06-13T05:36:03Z
2018-06-13T05:36:03Z
10.1002/jgt.22365
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22365?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22365?af=R
Highly edge‐connected factors using given lists on degrees
Abstract
Let G be a 2k‐edge‐connected graph with and let for every . A spanning subgraph F of G is called an L‐factor, if for every . In this article, we show that if for every , then G has a k‐edge‐connected L‐factor. We also show that if and for every , then G has a k‐edge‐connected L‐factor.
SaieedAkbari
,
MortezaHasanvand
,
KentaOzeki
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/VQWJrLyPZh0/jgt.22373
]]>
Journal of Graph Theory, EarlyView. <br/>
Highly edge‐connected factors using given lists on degrees
doi:10.1002/jgt.22373
Journal of Graph Theory
2018-06-13T05:40:10Z
Journal of Graph Theory
2018-06-13T05:40:10Z
2018-06-13T05:40:10Z
10.1002/jgt.22373
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22373?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22373?af=R
Sufficient conditions for the existence of a path‐factor which are related to odd components
Abstract
In this article, we are concerned with sufficient conditions for the existence of a ‐factor. We prove that for , there exists such that if a graph G satisfies for all , then G has a ‐factor, where is the number of components C of with . On the other hand, we construct infinitely many graphs G having no ‐factor such that for all .
YoshimiEgawa
,
MichitakaFuruya
,
KentaOzeki
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/GHgl_IJh8mg/jgt.22253
]]>
Journal of Graph Theory, EarlyView. <br/>
Sufficient conditions for the existence of a path‐factor which are related to odd components
doi:10.1002/jgt.22253
Journal of Graph Theory
2018-04-20T07:00:00Z
Journal of Graph Theory
2018-04-20T07:00:00Z
2018-04-20T07:00:00Z
10.1002/jgt.22253
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22253?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22253?af=R
Pairs and triples of forbidden subgraphs and the existence of a 2‐factor
Abstract
Let be a set of connected graphs, each of which has order at least three, and suppose that there exist infinitely many connected ‐free graphs of minimum degree at least two and all except for finitely many of them have a 2‐factor. In [J. Graph Theory, 64
(2010), 250–266], we proved that if , then one of the members in is a star. In this article, we determine the remaining members of and hence give a complete characterization of the pairs and triples of forbidden subgraphs.
R. E. L.Aldred
,
JunFujisawa
,
AkiraSaito
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/sXZ9kQhOD70/jgt.22368
]]>
Journal of Graph Theory, EarlyView. <br/>
Pairs and triples of forbidden subgraphs and the existence of a 2‐factor
doi:10.1002/jgt.22368
Journal of Graph Theory
2018-06-15T06:11:15Z
Journal of Graph Theory
2018-06-15T06:11:15Z
2018-06-15T06:11:15Z
10.1002/jgt.22368
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22368?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22368?af=R
The homomorphism threshold of ‐free graphs
Abstract
We determine the structure of ‐free graphs with n vertices and minimum degree larger than : such graphs are homomorphic to the graph obtained from a ‐cycle by adding all chords of length , for some k. This answers a question of Messuti and Schacht. We deduce that the homomorphism threshold of ‐free graphs is 1/5, thus answering a question of Oberkampf and Schacht.
ShohamLetzter
,
RichardSnyder
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/S_dFU5U2j_o/jgt.22369
]]>
Journal of Graph Theory, EarlyView. <br/>
The homomorphism threshold of ‐free graphs
doi:10.1002/jgt.22369
Journal of Graph Theory
2018-06-19T04:46:46Z
Journal of Graph Theory
2018-06-19T04:46:46Z
2018-06-19T04:46:46Z
10.1002/jgt.22369
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22369?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22369?af=R
On the local density problem for graphs of given odd‐girth
Abstract
Erdős conjectured that every n‐vertex triangle‐free graph contains a subset of vertices that spans at most edges. Extending a recent result of Norin and Yepremyan, we confirm this conjecture for graphs homomorphic to so‐called Andrásfai graphs. As a consequence, Erdős' conjecture holds for every triangle‐free graph G with minimum degree and if the degree condition can be relaxed to . In fact, we obtain a more general result for graphs of higher odd‐girth.
WiebkeBedenknecht
,
Guilherme OliveiraMota
,
ChristianReiher
,
MathiasSchacht
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/bKozvtkxZ34/jgt.22372
]]>
Journal of Graph Theory, EarlyView. <br/>
On the local density problem for graphs of given odd‐girth
doi:10.1002/jgt.22372
Journal of Graph Theory
2018-06-20T07:11:25Z
Journal of Graph Theory
2018-06-20T07:11:25Z
2018-06-20T07:11:25Z
10.1002/jgt.22372
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22372?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22372?af=R