Factors of claw-free graphs
Finding Tricyclic Graphs with a Maximal Number of Matchings - Another Example of Computer Aided Research in Graph Theory
Fractional Aspects of the Erdős-Faber-Lovász Conjecture
The Erdős-Faber-Lovász conjecture is the statement that every graph that is the union of n cliques of size n intersecting pairwise in at most one vertex has chromatic number n. Kahn and Seymour proved a fractional version of this conjecture, where the chromatic number is replaced by the fractional chromatic number. In this note we investigate similar fractional relaxations of the Erdős-Faber-Lovász conjecture, involving variations of the fractional chromatic number. We exhibit some relaxations that...
Fractional biclique covers and partitions of graphs.
Fractional Q-Edge-Coloring of Graphs
An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let [...] be an additive hereditary property of graphs. A [...] -edge-coloring of a simple graph is an edge coloring in which the edges colored with the same color induce a subgraph of property [...] . In this paper we present some results on fractional [...] -edge-colorings. We determine the fractional [...] -edge chromatic number for matroidal properties of graphs.
Front-divisors of trees.
Further results on vertex covering of powers of complete graphs.
General symmetric starter of orthogonal double covers of complete bipartite graph.
Generalizations of the tree packing conjecture
The Gyárfás tree packing conjecture asserts that any set of trees with 2,3,...,k vertices has an (edge-disjoint) packing into the complete graph on k vertices. Gyárfás and Lehel proved that the conjecture holds in some special cases. We address the problem of packing trees into k-chromatic graphs. In particular, we prove that if all but three of the trees are stars then they have a packing into any k-chromatic graph. We also consider several other generalizations of the conjecture.
Generalized connectivity of some total graphs
We study the generalized -connectivity as introduced by Hager in 1985, as well as the more recently introduced generalized -edge-connectivity . We determine the exact value of and for the line graphs and total graphs of trees, unicyclic graphs, and also for complete graphs for the case .
Generalized list colourings of graphs
We prove: (1) that can be arbitrarily large, where and are P-choice and P-chromatic numbers, respectively, (2) the (P,L)-colouring version of Brooks’ and Gallai’s theorems.
Graph factorization, general triple systems, and cyclic triple systems.
Graph products and new solutions to Oberwolfach problems.
Graphical condensation, overlapping Pfaffians and superpositions of matchings.
Graphs with greatest number of matchings.
Graphs with Large Generalized (Edge-)Connectivity
The generalized k-connectivity κk(G) of a graph G, introduced by Hager in 1985, is a nice generalization of the classical connectivity. Recently, as a natural counterpart, we proposed the concept of generalized k-edge-connectivity λk(G). In this paper, graphs of order n such that [...] for even k are characterized.
Graphs with maximum and minimum independence numbers.
Hamilton decompositions and -factorizations of hypercubes.
Hamilton decompositions of line graphs of some bipartite graphs
Some bipartite Hamilton decomposable graphs that are regular of degree δ ≡ 2 (mod 4) are shown to have Hamilton decomposable line graphs. One consequence is that every bipartite Hamilton decomposable graph G with connectivity κ(G) = 2 has a Hamilton decomposable line graph L(G).
Hamiltonian connectedness and a matching in powers of connected graphs
In this paper the following results are proved: 1. Let be a path with vertices, where and . Let be a matching in . Then is hamiltonian-connected. 2. Let be a connected graph of order , and let be a matching in . Then is hamiltonian-connected.