Calculating the number of the linear factors in planar graphs.
Characteristics And Maching Polynomials Of Some Compound Graphs
Characterization of magic graphs
Clique packings and clique partitions of graphs without odd chordless cycles
In this paper we consider partitions (resp. packings) of graphs without odd chordless cycles into cliques of order at least 2. We give a structure theorem, min-max results and characterization theorems for this kind of partitions and packings.
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.
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].