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
Partition functions and a generalized coloring‐flow duality for embedded graphs
Abstract
Let G be a finite group and a class function. Let be a directed graph with for each vertex a cyclic order of the edges incident to it. The cyclic orders give a collection F of faces of H. Define the partition function , where denotes the product of the κ‐values of the edges incident with v (in cyclic order), where the inverse is taken for edges leaving v. Write , where the sum runs over irreducible representations λ of G with character and with for every λ. When H is connected, it is proved that , where 1 is the identity element of G. Among the corollaries, a formula for the number of nowhere‐identity G‐flows on H is derived, generalizing a result of Tutte. We show that these flows correspond bijectively to certain proper G‐colorings of a covering graph of the dual graph of H. This correspondence generalizes coloring‐flow duality for planar graphs.
BartLitjens
,
BartSevenster
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/8l3VbvQ4ea4/jgt.22210
Volume 88, Issue 2, Page 271-283, June 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 2, Page 271-283, June 2018. <br/>
Partition functions and a generalized coloring‐flow duality for embedded graphs
doi:10.1002/jgt.22210
Journal of Graph Theory
2017-11-06T08:00:00Z
Journal of Graph Theory
88
2
2017-11-06T08:00:00Z
2017-11-06T08:00:00Z
10.1002/jgt.22210
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22210?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22210?af=R
Disjoint perfect matchings in 3‐uniform hypergraphs
Abstract
For a hypergraph H, let denote the minimum vertex degree in H. Kühn, Osthus, and Treglown proved that, for any sufficiently large integer n with , if H is a 3‐uniform hypergraph with order n and then H has a perfect matching, and this bound on is best possible. In this article, we show that under the same conditions, H contains at least pairwise disjoint perfect matchings, and this bound is sharp.
HongliangLu
,
XingxingYu
,
LiZhang
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/0OXzmsP7EE4/jgt.22211
Volume 88, Issue 2, Page 284-293, June 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 2, Page 284-293, June 2018. <br/>
Disjoint perfect matchings in 3‐uniform hypergraphs
doi:10.1002/jgt.22211
Journal of Graph Theory
2017-11-21T08:00:00Z
Journal of Graph Theory
88
2
2017-11-21T08:00:00Z
2017-11-21T08:00:00Z
10.1002/jgt.22211
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22211?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22211?af=R
A simple formula for the number of spanning trees of line graphs
Abstract
Suppose is a loopless graph and is the graph obtained from G by subdividing each of its edges k () times. Let be the set of all spanning trees of G, be the line graph of the graph and be the number of spanning trees of . By using techniques from electrical networks, we first obtain the following simple formula:
Then we find it is in fact equivalent to a complicated formula obtained recently using combinatorial techniques in [F. M. Dong and W. G. Yan, Expression for the number of spanning trees of line graphs of arbitrary connected graphs, J. Graph Theory. 85 (2017) 74–93].
HelinGong
,
Xian'anJin
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/2tcAcoltN9o/jgt.22212
Volume 88, Issue 2, Page 294-301, June 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 2, Page 294-301, June 2018. <br/>
A simple formula for the number of spanning trees of line graphs
doi:10.1002/jgt.22212
Journal of Graph Theory
2017-11-06T08:00:00Z
Journal of Graph Theory
88
2
2017-11-06T08:00:00Z
2017-11-06T08:00:00Z
10.1002/jgt.22212
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22212?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22212?af=R
On the possible values of the entropy of undirected graphs
Abstract
The entropy of a digraph is a fundamental measure that relates network coding, information theory, and fixed points of finite dynamical systems. In this article, we focus on the entropy of undirected graphs. We prove any bounded interval only contains finitely many possible values of the entropy of an undirected graph. We also determine all the possible values for the entropy of an undirected graph up to the value of four.
MaximilienGadouleau
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/tOUKp3e5T1o/jgt.22213
Volume 88, Issue 2, Page 302-311, June 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 2, Page 302-311, June 2018. <br/>
On the possible values of the entropy of undirected graphs
doi:10.1002/jgt.22213
Journal of Graph Theory
2017-11-09T08:00:00Z
Journal of Graph Theory
88
2
2017-11-09T08:00:00Z
2017-11-09T08:00:00Z
10.1002/jgt.22213
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22213?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22213?af=R
χ‐bounds, operations, and chords
Abstract
A long unichord in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is long unichord free if it does not contain any long unichord. We prove a structure theorem for long unichord free graph. We give an time algorithm to recognize them. We show that any long unichord free graph G can be colored with at most colors, where ω is the maximum number of pairwise adjacent vertices in G.
NicolasTrotignon
,
Lan AnhPham
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/WOicvCPCeNQ/jgt.22214
Volume 88, Issue 2, Page 312-336, June 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 2, Page 312-336, June 2018. <br/>
χ‐bounds, operations, and chords
doi:10.1002/jgt.22214
Journal of Graph Theory
2017-11-23T08:00:00Z
Journal of Graph Theory
88
2
2017-11-23T08:00:00Z
2017-11-23T08:00:00Z
10.1002/jgt.22214
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22214?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22214?af=R
A generalization of Gale's lemma
Abstract
In this work, we present a generalization of Gale's lemma. Using this generalization, we introduce two sharp combinatorial lower bounds for and , the two classic topological lower bounds for the chromatic number of a graph G.
MeysamAlishahi
,
HosseinHajiabolhassan
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/PU_0jEqUdqM/jgt.22215
Volume 88, Issue 2, Page 337-346, June 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 2, Page 337-346, June 2018. <br/>
A generalization of Gale's lemma
doi:10.1002/jgt.22215
Journal of Graph Theory
2017-11-13T08:00:00Z
Journal of Graph Theory
88
2
2017-11-13T08:00:00Z
2017-11-13T08:00:00Z
10.1002/jgt.22215
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22215?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22215?af=R
Clique minors in double‐critical graphs
Abstract
A connected t‐chromatic graph G is double‐critical if is ‐colorable for each edge . A long‐standing conjecture of Erdős and Lovász that the complete graphs are the only double‐critical t‐chromatic graphs remains open for all . Given the difficulty in settling Erdős and Lovász's conjecture and motivated by the well‐known Hadwiger's conjecture, Kawarabayashi, Pedersen, and Toft proposed a weaker conjecture that every double‐critical t‐chromatic graph contains a minor and verified their conjecture for . Albar and Gonçalves recently proved that every double‐critical 8‐chromatic graph contains a K8 minor, and their proof is computer assisted. In this article, we prove that every double‐critical t‐chromatic graph contains a minor for all . Our proof for is shorter and computer free.
MartinRolek
,
Zi‐XiaSong
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/ebmPf3-v_Xg/jgt.22216
Volume 88, Issue 2, Page 347-355, June 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 2, Page 347-355, June 2018. <br/>
Clique minors in double‐critical graphs
doi:10.1002/jgt.22216
Journal of Graph Theory
2017-11-15T08:00:00Z
Journal of Graph Theory
88
2
2017-11-15T08:00:00Z
2017-11-15T08:00:00Z
10.1002/jgt.22216
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22216?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22216?af=R
Dominating sets inducing large components in maximal outerplanar graphs
Abstract
For a maximal outerplanar graph G of order n at least three, Matheson and Tarjan showed that G has domination number at most . Similarly, for a maximal outerplanar graph G of order n at least five, Dorfling, Hattingh, and Jonck showed, by a completely different approach, that G has total domination number at most unless G is isomorphic to one of two exceptional graphs of order 12.
We present a unified proof of a common generalization of these two results. For every positive integer k, we specify a set of graphs of order at least and at most such that every maximal outerplanar graph G of order n at least that does not belong to has a dominating set D of order at most such that every component of the subgraph of G induced by D has order at least k.
José D.Alvarado
,
SimoneDantas
,
DieterRautenbach
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/_j_F4Xo4U3c/jgt.22217
Volume 88, Issue 2, Page 356-370, June 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 2, Page 356-370, June 2018. <br/>
Dominating sets inducing large components in maximal outerplanar graphs
doi:10.1002/jgt.22217
Journal of Graph Theory
2017-11-14T08:00:00Z
Journal of Graph Theory
88
2
2017-11-14T08:00:00Z
2017-11-14T08:00:00Z
10.1002/jgt.22217
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22217?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22217?af=R
A relaxation of the strong Bordeaux Conjecture
Abstract
Let be k nonnegative integers. A graph G is ‐colorable if the vertex set can be partitioned into k sets , such that the subgraph , induced by , has maximum degree at most for . Let denote the family of plane graphs with neither adjacent 3‐cycles nor 5‐cycles. Borodin and Raspaud (2003) conjectured that each graph in is (0, 0, 0)‐colorable (which was disproved very recently). In this article, we prove that each graph in is (1, 1, 0)‐colorable, which improves the results by Xu (2009) and Liu‐Li‐Yu (2016).
ZiwenHuang
,
XiangwenLi
,
GexinYu
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/rET8rFG3khc/jgt.22208
Volume 88, Issue 2, Page 237-254, June 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 2, Page 237-254, June 2018. <br/>
A relaxation of the strong Bordeaux Conjecture
doi:10.1002/jgt.22208
Journal of Graph Theory
2017-11-08T08:00:00Z
Journal of Graph Theory
88
2
2017-11-08T08:00:00Z
2017-11-08T08:00:00Z
10.1002/jgt.22208
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22208?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22208?af=R
On unavoidable‐induced subgraphs in large prime graphs
Abstract
Chudnovsky, Kim, Oum, and Seymour recently established that any prime graph contains one of a short list of induced prime subgraphs [1]. In the present article, we reprove their theorem using many of the same ideas, but with the key model‐theoretic ingredient of first determining the so‐called amount of stability of the graph. This approach changes the applicable Ramsey theorem, improves the bounds and offers a different structural perspective on the graphs in question. Complementing this, we give an infinitary proof that implies the finite result.
M.Malliaris
,
C.Terry
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/IMCPVjWp-cs/jgt.22209
Volume 88, Issue 2, Page 255-270, June 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 2, Page 255-270, June 2018. <br/>
On unavoidable‐induced subgraphs in large prime graphs
doi:10.1002/jgt.22209
Journal of Graph Theory
2017-11-15T08:00:00Z
Journal of Graph Theory
88
2
2017-11-15T08:00:00Z
2017-11-15T08:00:00Z
10.1002/jgt.22209
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22209?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22209?af=R
Issue Information
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/kSVRxdf9I8E/jgt.22195
Volume 88, Issue 2, Page 233-235, June 2018.

]]>
Journal of Graph Theory, Volume 88, Issue 2, Page 233-235, June 2018. <br/>
Issue Information
doi:10.1002/jgt.22195
Journal of Graph Theory
2018-04-15T08:19:53Z
Journal of Graph Theory
88
2
2018-04-15T08:19:53Z
2018-04-15T08:19:53Z
10.1002/jgt.22195
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22195?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22195?af=R
Sharp Dirac's theorem for DP‐critical graphs
Abstract
Correspondence coloring, or DP‐coloring, is a generalization of list coloring introduced recently by Dvořák and Postle [11]. In this article, we establish a version of Dirac's theorem on the minimum number of edges in critical graphs [9] in the framework of DP‐colorings. A corollary of our main result answers a question posed by Kostochka and Stiebitz [15] on classifying list‐critical graphs that satisfy Dirac's bound with equality.
AntonBernshteyn
,
AlexandrKostochka
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/1dvoz-bfRbg/jgt.22227
]]>
Journal of Graph Theory, EarlyView. <br/>
Sharp Dirac's theorem for DP‐critical graphs
doi:10.1002/jgt.22227
Journal of Graph Theory
2017-12-18T08:00:00Z
Journal of Graph Theory
2017-12-18T08:00:00Z
2017-12-18T08:00:00Z
10.1002/jgt.22227
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22227?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22227?af=R
A greedy algorithm for finding a large 2‐matching on a random cubic graph
Abstract
A 2‐matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2‐matching U is the number of edges in U and this is at least where n is the number of vertices of G and κ denotes the number of components. In this article, we analyze the performance of a greedy algorithm 2greedy for finding a large 2‐matching on a random 3‐regular graph. We prove that with high probability, the algorithm outputs a 2‐matching U with .
DeepakBal
,
PatrickBennett
,
TomBohman
,
AlanFrieze
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/q8sYpLndX3k/jgt.22224
]]>
Journal of Graph Theory, EarlyView. <br/>
A greedy algorithm for finding a large 2‐matching on a random cubic graph
doi:10.1002/jgt.22224
Journal of Graph Theory
2017-11-27T08:00:00Z
Journal of Graph Theory
2017-11-27T08:00:00Z
2017-11-27T08:00:00Z
10.1002/jgt.22224
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22224?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22224?af=R
Clique coloring of dense random graphs
Abstract
The clique chromatic number of a graph is the minimum number of colors in a vertex coloring so that no maximal (with respect to containment) clique is monochromatic. We prove that the clique chromatic number of the binomial random graph is, with high probability, . This settles a problem of McDiarmid, Mitsche, and Prałat who proved that it is with high probability.
NogaAlon
,
MichaelKrivelevich
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/zru38xhMQt4/jgt.22222
]]>
Journal of Graph Theory, EarlyView. <br/>
Clique coloring of dense random graphs
doi:10.1002/jgt.22222
Journal of Graph Theory
2017-11-28T08:00:00Z
Journal of Graph Theory
2017-11-28T08:00:00Z
2017-11-28T08:00:00Z
10.1002/jgt.22222
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22222?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22222?af=R
Full subgraphs
Abstract
Let be a graph of density p on n vertices. Following Erdős, Łuczak, and Spencer, an m‐vertex subgraph H of G is called full if H has minimum degree at least . Let denote the order of a largest full subgraph of G. If is a nonnegative integer, define
Erdős, Łuczak, and Spencer proved that for ,
In this article, we prove the following lower bound: for ,
Furthermore, we show that this is tight up to a multiplicative constant factor for infinitely many p near the elements of . In contrast, we show that for any n‐vertex graph G, either G or contains a full subgraph on vertices. Finally, we discuss full subgraphs of random and pseudo‐random graphs, and several open problems.
Victor Falgas‐Ravry
,
KlasMarkström
,
JacquesVerstraëte
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/Crf99oKkW7M/jgt.22221
]]>
Journal of Graph Theory, EarlyView. <br/>
Full subgraphs
doi:10.1002/jgt.22221
Journal of Graph Theory
2017-11-16T08:00:00Z
Journal of Graph Theory
2017-11-16T08:00:00Z
2017-11-16T08:00:00Z
10.1002/jgt.22221
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22221?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22221?af=R
The decycling number and maximum genus of cubic graphs
Abstract
Let and denote the minimum size of a decycling set and maximum genus of a graph G, respectively. For a connected cubic graph G of order n, it is shown that . Applying the formula, we obtain some new results on the decycling number and maximum genus of cubic graphs. Furthermore, it is shown that the number of vertices of a decycling set S in a k‐regular graph G is , where c and are the number of components of and the number of edges in , respectively. Therefore, S is minimum if and only if is minimum. As an application, this leads to a lower bound for of a k‐regular graph G. In many cases this bound may be sharp.
ShudeLong
,
HanRen
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/F8d9vSfKpGc/jgt.22218
]]>
Journal of Graph Theory, EarlyView. <br/>
The decycling number and maximum genus of cubic graphs
doi:10.1002/jgt.22218
Journal of Graph Theory
2017-11-17T08:00:00Z
Journal of Graph Theory
2017-11-17T08:00:00Z
2017-11-17T08:00:00Z
10.1002/jgt.22218
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22218?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22218?af=R
Covering 2‐connected 3‐regular graphs with disjoint paths
Abstract
A path cover of a graph is a set of disjoint paths so that every vertex in the graph is contained in one of the paths. The path cover number of graph G is the cardinality of a path cover with the minimum number of paths. Reed in 1996 conjectured that a 2‐connected 3‐regular graph has path cover number at most . In this article, we confirm this conjecture.
GexinYu
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/5zhwGT8nHN8/jgt.22219
]]>
Journal of Graph Theory, EarlyView. <br/>
Covering 2‐connected 3‐regular graphs with disjoint paths
doi:10.1002/jgt.22219
Journal of Graph Theory
2017-11-14T08:00:00Z
Journal of Graph Theory
2017-11-14T08:00:00Z
2017-11-14T08:00:00Z
10.1002/jgt.22219
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22219?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22219?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
]]>
Journal of Graph Theory, EarlyView. <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
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
]]>
Journal of Graph Theory, EarlyView. <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
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
Improved bounds for minimal feedback vertex sets in tournaments
Abstract
We study feedback vertex sets (FVS) in tournaments, which are orientations of complete graphs. As our main result, we show that any tournament on n nodes has at most 1.5949n minimal FVS. This significantly improves the previously best upper bound of 1.6667n by Fomin et al. [STOC 2016] and 1.6740n by Gaspers and Mnich [J. Graph Theory 72(1):72–89, 2013]. Our new upper bound almost matches the best‐known lower bound of , due to Gaspers and Mnich. Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time .
M.Mnich
,
E.Teutrine
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/TTKElrlvaow/jgt.22225
]]>
Journal of Graph Theory, EarlyView. <br/>
Improved bounds for minimal feedback vertex sets in tournaments
doi:10.1002/jgt.22225
Journal of Graph Theory
2017-12-08T08:00:00Z
Journal of Graph Theory
2017-12-08T08:00:00Z
2017-12-08T08:00:00Z
10.1002/jgt.22225
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22225?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22225?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
]]>
Journal of Graph Theory, EarlyView. <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
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
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
]]>
Journal of Graph Theory, EarlyView. <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
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
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
]]>
Journal of Graph Theory, EarlyView. <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
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
On Hamilton decompositions of infinite circulant graphs
Abstract
The natural infinite analog of a (finite) Hamilton cycle is a two‐way‐infinite Hamilton path (connected spanning 2‐valent subgraph). Although it is known that every connected 2k‐valent infinite circulant graph has a two‐way‐infinite Hamilton path, there exist many such graphs that do not have a decomposition into k edge‐disjoint two‐way‐infinite Hamilton paths. This contrasts with the finite case where it is conjectured that every 2k‐valent connected circulant graph has a decomposition into k edge‐disjoint Hamilton cycles. We settle the problem of decomposing 2k‐valent infinite circulant graphs into k edge‐disjoint two‐way‐infinite Hamilton paths for , in many cases when , and in many other cases including where the connection set is or .
DarrynBryant
,
SaradaHerke
,
BarbaraMaenhaut
,
Bridget S.Webb
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/MIYq_Ceywbc/jgt.22223
]]>
Journal of Graph Theory, EarlyView. <br/>
On Hamilton decompositions of infinite circulant graphs
doi:10.1002/jgt.22223
Journal of Graph Theory
2017-12-22T08:00:00Z
Journal of Graph Theory
2017-12-22T08:00:00Z
2017-12-22T08:00:00Z
10.1002/jgt.22223
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22223?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22223?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
]]>
Journal of Graph Theory, EarlyView. <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
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
]]>
Journal of Graph Theory, EarlyView. <br/>
Decomposing planar cubic graphs
doi:10.1002/jgt.22234
Journal of Graph Theory
2018-01-10T08:00:00Z
Journal of Graph Theory
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
Decomposition of complete uniform multi‐hypergraphs into Berge paths and cycles
Abstract
In 2015, Bryant, Horsley, Maenhaut, and Smith, generalizing a well‐known conjecture by Alspach, obtained the necessary and sufficient conditions for the decomposition of the complete multigraph into cycles of arbitrary lengths, where I is empty, when is even and I is a perfect matching, when is odd. Moreover, Bryant in 2010, verifying a conjecture by Tarsi, proved that the obvious necessary conditions for packing pairwise edge‐disjoint paths of arbitrary lengths in are also sufficient. In this article, first, we obtain the necessary and sufficient conditions for packing edge‐disjoint cycles of arbitrary lengths in . Then, applying this result, we investigate the analogous problem of the decomposition of the complete uniform multihypergraph into Berge cycles and paths of arbitrary given lengths. In particular, we show that for every integer , and , can be decomposed into Berge cycles and paths of arbitrary lengths, provided that the obvious necessary conditions hold, thereby generalizing a result by Kühn and Osthus on the decomposition of into Hamilton Berge cycles.
RaminJavadi
,
AfsanehKhodadadpour
,
GholamrezaOmidi
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/fJP-hfYsqp4/jgt.22226
]]>
Journal of Graph Theory, EarlyView. <br/>
Decomposition of complete uniform multi‐hypergraphs into Berge paths and cycles
doi:10.1002/jgt.22226
Journal of Graph Theory
2017-12-06T08:00:00Z
Journal of Graph Theory
2017-12-06T08:00:00Z
2017-12-06T08:00:00Z
10.1002/jgt.22226
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22226?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22226?af=R
Families of locally separated Hamilton paths
Abstract
We improve by an exponential factor the lower bound of Körner and Muzi for the cardinality of the largest family of Hamilton paths in a complete graph of n vertices in which the union of any two paths has maximum degree 4. The improvement is through an explicit construction while the previous bound was obtained by a greedy algorithm. We solve a similar problem for permutations up to an exponential factor.
JánosKörner
,
AngeloMonti
http://feedproxy.google.com/~r/wileyonlinelibrary/jgt/~3/mf5MfZSy5Rs/jgt.22220
]]>
Journal of Graph Theory, EarlyView. <br/>
Families of locally separated Hamilton paths
doi:10.1002/jgt.22220
Journal of Graph Theory
2017-11-10T08:00:00Z
Journal of Graph Theory
2017-11-10T08:00:00Z
2017-11-10T08:00:00Z
10.1002/jgt.22220
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22220?af=R
https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22220?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
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-20T06:34:05Z
Journal of Graph Theory
2018-04-20T06:34:05Z
2018-04-20T06:34:05Z
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
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