Name
Abstract | ||
|---|---|---|
Let G be a connected simple graph on n vertices. Gallai's conjecture asserts that the edges of G can be decomposed into ⌈n/2⌉ paths. Let H be the subgraph induced by the vertices of even degree in G. Lovász showed that the conjecture is true if H contains at most one vertex. Extending Lovász's result, Pyber proved that the conjecture is true if H is a forest. A forest can be regarded as a graph in which each block is an isolated vertex or a single edge (and so each block has maximum degree at most 1). In this paper, we show that the conjecture is true if H can be obtained from the emptyset by a series of so-defined α-operations. As a corollary, the conjecture is true if each block of H is a triangle-free graph of maximum degree at most 3. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.jctb.2004.09.008 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
isolated vertex,maximum degree,n vertex,g. lov,decomposition,extending lov,path,connected simple graph,path decomposition,single edge,triangle-free graph,gallai's conjecture | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Lonely runner conjecture,Degree (graph theory),New digraph reconstruction conjecture,Corollary,Conjecture,Collatz conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
93 | 2 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
14 | 1.76 | 4 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Genghua Fan | 1 | 412 | 65.22 |