Search
Search Results
-
Compatible Spanning Circuits and Forbidden Induced Subgraphs
A compatible spanning circuit in an edge-colored graph G (not necessarily properly) is defined as a closed trail containing all vertices of G in...
-
Domination and Forbidden Subgraphs
Uncorrected In this chapter, we study the three core domination parameters in graphs with specific structural restrictions imposed, such as...
-
Forbidden subgraphs in enhanced power graphs of finite groups
The enhanced power graph of a group is the simple graph whose vertex set is consisted of all elements of the group, and whose any pair of vertices...
-
A Complete Complexity Dichotomy of the Edge-Coloring Problem for All Sets of \(8\)-Edge Forbidden Subgraphs
AbstractFor a given graph, the edge-coloring problem is to minimize the number of colors sufficient to color all the graph edges so that any...
-
The Game of Cops and Robbers on Directed Graphs with Forbidden Subgraphs
The traditional game of cops and robbers is played on undirected graph. Recently, the same game played on directed graph is getting attention by more...
-
Edge Contraction and Forbidden Induced Subgraphs
Given a family of graphs \(\mathcal {H}\) , a graph G is...
-
Toughness, Forbidden Subgraphs and Pancyclicity
Motivated by several conjectures due to Nikoghosyan, in a recent article due to Li et al., the aim was to characterize all possible graphs H such...
-
Estimates of the Number of Edges in Subgraphs of Johnson Graphs
AbstractWe consider special distance graphs and estimate the number of edges in their subgraphs. The estimates obtained improve some known...
-
Some Cases of Polynomial Solvability of the Edge Coloring Problem That Are Generated by Forbidden 8-Edge Subcubic Forests
AbstractThe edge-coloring problem is to minimize the number of colors sufficient to color all the edges of a given graph so that any adjacent edges...
-
-
On the Minimal Number of Edges in Induced Subgraphs of Special Distance Graphs
AbstractThree new theorems are proved in the paper, which give bounds for the number of edges in induced subgraphs of a special distance graph.
... -
Forbidden Subgraphs for a Graph to Have a Hamiltonian Path Square
The square of a graph is obtained by adding an edge between each pair of vertices that are of distance 2 in the original graph. If a graph G has a...
-
Forbidden Odds, Binaries, and Factorials
In March 1994, I arrived in Florida Atlantic University for the 25th Southeastern International Conference on Combinatorics, Graph Theory, and...
-
Forbidden Pairs for Connected Even Factors in Supereulerian Graphs
A graph is called supereulerian if it has a spanning eulerian subgraph. A connected even [2, 2s]-factor of a graph G is a connected factor with all...
-
Complete Complexity Dichotomy for \(\boldsymbol 7 \)-Edge Forbidden Subgraphs in the Edge Coloring Problem
AbstractThe edge coloring problem for a graph is to minimize the number of colors that are sufficient to color all edges of the graph so that all...
-
General Structure Under Forbidden Rainbow Subgraphs
The general structure of colored complete graphs containing no copy of a particular rainbow subgraph has been extremely useful in establishing sharp...
-
Maximum bipartite subgraphs in H-free graphs
Given a graph G , let f ( G ) denote the maximum number of edges in a bipartite subgraph of G . Given a fixed graph H and a positive integer m , let f ( m, H )...