Co prime path decomposition number of a graph.
Coloring of graphs by partitioning
Combinatorial properties of products of graphs
Complementarily domatic number of a graph
Complete minors, independent sets, and chordal graphs
The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) ≥ χ(G). Since χ(G) α(G) ≥ |V(G)|, Hadwiger's Conjecture implies that α(G) h(G) ≥ |V(G)|. We show that (2α(G) - ⌈log_{τ}(τα(G)/2)⌉) h(G) ≥ |V(G)| where τ ≍ 6.83. For graphs with α(G) ≥ 14, this improves on a recent result of Kawarabayashi and Song who showed (2α(G) - 2) h(G) ≥ |V(G) | when α(G) ≥ 3.
Complexité de l'arboricité linéaire d'un graphe II
Complexity of decomposing graphs into factors with given diameters or radii
Connected domatic number in planar graphs
A dominating set in a graph is a connected dominating set of if it induces a connected subgraph of . The connected domatic number of is the maximum number of pairwise disjoint, connected dominating sets in . We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3.
Connections between the matching and chromatic polynomials.
"Correction Of The Paper ""Graphs With Greatest Number Of Matchings"""
Counting perfect matchings in polyominoes with an application to the dimer problem
Covering and packing in graphs. III: Cyclic and acyclic invariants
Covers of digraphs
Cycle Double Covers of Infinite Planar Graphs
In this paper, we study the existence of cycle double covers for infinite planar graphs. We show that every infinite locally finite bridgeless k-indivisible graph with a 2-basis admits a cycle double cover.
Cyclic decompositions of complete graphs into spanning trees
We examine decompositions of complete graphs with an even number of vertices, , into n isomorphic spanning trees. While methods of such decompositions into symmetric trees have been known, we develop here a more general method based on a new type of vertex labelling, called flexible q-labelling. This labelling is a generalization of labellings introduced by Rosa and Eldergill.
Cyclically 5-edge connected non-bicritical critical snarks
Snarks are bridgeless cubic graphs with chromatic index χ' = 4. A snark G is called critical if χ'(G-{v,w}) = 3, for any two adjacent vertices v and w. For any k ≥ 2 we construct cyclically 5-edge connected critical snarks G having an independent set I of at least k vertices such that χ'(G-I) = 4. For k = 2 this solves a problem of Nedela and Skoviera [6].
Decomposing complete graphs into cubes
This paper concerns when the complete graph on n vertices can be decomposed into d-dimensional cubes, where d is odd and n is even. (All other cases have been settled.) Necessary conditions are that n be congruent to 1 modulo d and 0 modulo . These are known to be sufficient for d equal to 3 or 5. For larger values of d, the necessary conditions are asymptotically sufficient by Wilson’s results. We prove that for each odd d there is an infinite arithmetic progression of even integers n for which...
Decomposing complete tripartite graphs into closed trails of arbitrary lengths
The complete tripartite graph has edges. For any collection of positive integers with and for , we exhibit an edge-disjoint decomposition of into closed trails (circuits) of lengths .
Decomposing infinite 2-connected graphs into 3-connected components.
Decomposition of a complete equipartite graph into isomorphic subgraphs