Journal of Graph Theory
Издатель: Wiley · ISSN 03649024 · 15 статей
-
A Characterization of P6‐Free Irredundance Perfect Graphs
ABSTRACT Let and denote the irredundance number and the domination number of a graph , respectively. A graph is said to be irredundance perfect if for every induced subgraph of . The class of ‐free irredundance perfect graphs has been...
-
Covering Multigraphs With Bipartite Graphs
ABSTRACT Hansel's lemma states , where is a collection of bipartite graphs covering all the edges of . We generalize this lemma to the corresponding multigraph covering problem and the graphon covering problem. We also prove an upper...
-
Toward Pancyclicity in 4‐Connected Planar Graphs
ABSTRACT We show that every edge in a 4‐connected planar graph on vertices is contained in at least cycles of pairwise distinct lengths. We also show that this number can be at best. In the case of 4‐connected planar graphs not...
-
Edge‐Coloring a Graph G so That Every Copy of a Graph H Has an Odd Color Class
ABSTRACT Recently, Alon introduced the notion of an ‐code for a graph : a collection of graphs on vertex set is an ‐code if it contains no two members whose symmetric difference is isomorphic to . Let denote the maximum possible...
-
A Generalization of an Ear Decomposition and k‐Trees in Highly Connected Star‐Free Graphs
ABSTRACT In this paper, we introduce a generalized version of an ear decomposition, called a ‐spider decomposition, for ‐connected star‐free graphs with . This application enables us to improve a previously known sufficient condition...
-
A Structural Description of Zykov and Blanche Descartes Graphs
ABSTRACT Around 1950, Zykov and Blanche Descartes proposed the two first explicit constructions of triangle‐free graphs with arbitrarily large chromatic number. We define a Zykov (resp. Blanche Descartes) graph as any induced subgraph...
-
The Turán Number of Berge Paths
ABSTRACT A Berge path of length in an ‐uniform hypergraph is a collection of hyperedges and vertices such that for each . Győri, Katona, and Lemons generalized the Erdős–Gallai theorem to Berge paths and established bounds for the Turán...
-
On the Turán Number of the G3×3 in Linear Hypergraphs
ABSTRACT We construct dense 3‐uniform linear hypergraphs without grids. This improves the known lower bound for their Turán number. We also discuss some related problems.
-
Vertex‐Based Localization of Erdős–Gallai Theorems for Paths and Cycles
ABSTRACT For a simple graph , let and denote the number of vertices and edges in , respectively. The Erdős–Gallai theorem for paths states that in a simple ‐free graph, , where denotes a path with length (i.e., with edges). In this...
- Issue Information
-
From Finding a Spanning Subgraph H to an H‐Factor
ABSTRACT A typical Dirac‐type problem in extremal graph theory is to determine the minimum degree threshold for a graph to have a spanning subgraph , for example, the Dirac theorem. A natural follow‐up problem is to seek an ‐factor,...
-
Flow‐Critical Graphs
ABSTRACT Lovász et al. proved that every six‐edge‐connected graph has a nowhere‐zero three‐flow. In fact, they proved a more technical statement, which says that there exists a nowhere‐zero three‐flow that extends the flow prescribed on...
-
The 13‐Conjectures for Domination in Cubic Graphs
ABSTRACT A set of vertices in a graph is a dominating set of if every vertex not in is adjacent to a vertex in . The domination number of , denoted by , is the minimum cardinality among all dominating sets in . In a breakthrough paper...
-
The Minimal Nonplanar Strong Digraphs
ABSTRACT Kuratowski's theorem says that the minimal (under subgraph containment) graphs that are not planar are the subdivisions of and of . Here we study the minimal (under subdigraph containment) strongly‐connected digraphs that are...
-
The Oriented Chromatic Number of Random Graphs of Bounded Degree
ABSTRACT The chromatic number of the random graph has long been studied and has inspired several landmark results. In the case where , Achlioptas and Naor showed the chromatic number is asymptotically two‐point concentrated. Kemkes et...